5

What is an efficient way to implement Adjacency List Representation of Graph in C++?

  1. vector *edges;
  2. list *edges;
  3. map<int, int> *edges;
  4. 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?

Smile001
  • 147
  • 3
  • 9
  • I would suggest **vector> adj_list**. for example **adj_list[1]** will represent all the vertices with which vertex 1 shares an edge. – Aditya_U Oct 16 '20 at 18:08
  • @Aditya_U What is wrong with option 3 or 4, a vector will take O(n) time for searching whether there is an edge between vertex u and v, but it can be done in very less time using maps data structure... If I will do edges[u], I will get a map of all the adjacent vertices of u and can perform operations efficiently... What do you have to say about this? – Smile001 Oct 17 '20 at 13:22

2 Answers2

5

What is an efficient way to implement Adjacency List Representation of Graph in C++

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 ordered std::map over the amortized constant-time lookup container std::unordered_map.

The associative containers std::unordered_map and std::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.

dfrib
  • 70,367
  • 12
  • 127
  • 192
  • What about this new 4th option I have now edited? Rather than using vectors, I will use map again for reducing the time for searching... – Smile001 Oct 16 '20 at 12:31
  • What is the advantage of using vectors over map, if I see performance including all the operations? – Smile001 Oct 16 '20 at 12:36
0

This is to especially address your fourth option.

You can take inspiration from Algorithms, 4th Edition by Sedgewick and Wayne and go with an array/vector of unordered_multisets (only neighbouring nodes in case of unweighted edges) or unordered_multimaps (neighbouring nodes and edges in case of weighted edges). In that book they use Java and work with the Bag data structure, which is an unordered collection of objects, with the possibility for duplicates.

The choice for the "outer" data structure could be an unordered_map also as suggested by @dfrib. As he says, one needs to measure for one's application to decide.

Hari
  • 1,561
  • 4
  • 17
  • 26