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

user_648945 0
Viewed 21632

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

graph data-structures c++ performance
4 Answers

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];

user_177065510

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.

user_72384360
Related