What is an efficient way to implement Adjacency List Representation of Graph in C++?
- vector *edges;
- list *edges;
- map<int, int> *edges;
- map<int, map<int, int>> edges;
In my opinion, it should be option 3 or 4, but I could not find any cons in using that... Are there any?
Can someone please help me, which will be the most efficient way of implementing the Adjacency List and also for Competitive Programming?
Many typical graph problems apply to a given static graph that will need to be represented once whereafter the given representation can be re-used whilst solving the related problem. In this case,
std::unordered_map<int, std::vector<int>>
is an appropriate structure; where the value for a given key in the unordered map represents the (single-/bi-directional) connected vertices for a given vertex. There should be no reason to use the orderedstd::map
over the amortized constant-time lookup containerstd::unordered_map
.The associative containers
std::unordered_map
andstd::unordered_set
are quick for lookup (which you want here), but can have performance implications if they need to mutate often (e.g. for a dynamic graph problem). As always, profiling and measuring runtime and memory to find bottlenecks for you actual problem implementation is key if you are implementing a highperf computation program.