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

Question

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 one 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

Answer 1

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.