Different ways for storing Graph

When it comes to Graph in most of the cases we prefer adjacency list representation over matrix representation.

In adjacency list representation we maintain list for every vertex as its name suggest.This list contain destination vertexes which are directly connected to current vertex via edge.So what are the ways to store such thing.

1. Array of vectors : Here we will take advantage of dynamic nature of vector.

vector< int > graph[ N ]

N is a static variable here vary according to constraints . One thing to notice here is that vector helped us in our job but its capacity changes in way that is more than what we need so we are wasting that memory. So this give rise to second way which is using list in place of vector.

2. Array of Lists : It has slow traversal as compared to vectors but insertion n deletion is quick.

list< int > graph[ N ]

In contests it hardly matters which of the above implementation you use they are both quite okay. You can also use vector instead of array in above two ways , So that you won’t have to worry about N being static anymore.

There are more ways that may come handy in some cases But mostly use method 1 or 2 to store graph.

3. Map of integer and list : Using map for storing graph can be expensive.

map< int , list< int > > graph

4. vector of sets : set has its own properties so this way it can also come handy in some cases.

vector< set > graph( N )

Method 1 and 2 are used quite often to see, for implementation using method 4 prefer code in this editorial.