What is the best standard data structure to build a Graph?

at first i am a beginner at c++ and i am self learning it, so please be quite simple in answers ...

i need to program a graph that contains nodes each node has id and list of edges each edge has the other node id and the distance

what i am looking for is what should i use to build this graph considering that i wants to use dijkstra algorithm to get the shortest path form o开发者_Python百科ne point to the other ... so searching performance should be the most important i think !!

i have searched a lot and i am so confused now

thank you in advance for the help

You can define an Edge structure like

struct Edge
{
    int destination;
    int weight;
};

And create a graph as

vector<vector<Edge> > graph;

Then to access all the edges coming from the vertex u, you write something like

for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    // here edge.destination and edge.weight give you some details.
}

You can dynamically add new edges, for example an edge from 3rd vertex to 7th with a weight of 8:

Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

etc.

For undirected graphs you should not forget to add the symmetric edge, of course.

This should do ok.

Edit The choice of base containers (std::vector, std::list, std::map) depends on the use case, e.g. what are you doing with the graph more often: add/remove vertices/edges, just traversing. Once your graph is created, either std::list or std::vector is equally good for Dijkstra, std::vector being a bit faster thanks to sequential access pattern of the relaxation stage.

Use unordered_map<int,vector<int>> to represent adjacency list if you have huge number of vertexes. If you're planning on implementing a small scale graph, then go with array of vectors. Eg: vector<int> v[20];

a graph that contains nodes each node has id and list of edges each edge has the other node id and the distance

If we consider each node id as an index. We can draw an nxn matrix of the edges as follows.

This can help you draw the graph with edges.

     [0][1][2][3]

[0] | 1  0  0  0|
[1] | 0  0  1  0|
[2] | 1  0  0  1|
[3] | 0  0  1  0|

So, a 2D array is a good representation of matrix.

int maxtrix[4][4] = new int[4][4];

I personally would use a std::map<Node*, std::set<Node*> >. This is extremely useful because each time you are at a node, you can quickly find out which nodes that node is connected to. It is also really easy to iterate over all the nodes if you need to. If you need to put weights on the edges, you could use std::map<Node*, std::set< std::pair<int, Node*> > >. This will give much better performance than using vectors, especially for large graphs.