I recently implemented DFS by making an adjacency list using a vector of vectors and was pretty pleased about that. But yesterday, I read here http://web.stanford.edu/class/cs97si/ on the basic Graph algorithms slide that an array of vectors is slower than plain arrays.
For me, vectors of vectors was pretty easy to code but just arrays was hard as I had trouble just adding an edge and manipulating the 2 arrays. What do the rest of you recommend me to use taking into account time and memory efficiency? If you recommend arrays, could you also give me a good resource which explains how to easily implement it?
Also, I read that we should use an adjacency matrix only when the graph is dense (No. of vertices is almost equal to no. of edges). But what if the constraints (around 10^5 edges) are such that it is too large even for the global scope? What do I use to represent the edge relations in such a case?
I have never come across any slowness issues using an array of vectors.
But do use an array of vectors, not a vector of vectors. Usually you know the number of vertexes, so
vector<int> e[MAXIMUM_NO_OF_VERTICES]
should be sufficient, where e[v][i] is the ith vertex that v is connected to. It’s also easier IMO than a vector of vectors.
Also, dense means that the number of edges is nearly the number of pairs of vertices, not number of vertexes.
A vertex with number of edges around the number of vertices is a very sparse graph.
An adjacency matrix is feasible only if N^2 is pretty small. For number of vertexes around 10^5 the size of an adjacency matrix is 4*10^10 (around 40 GB) which is certainly not going to fit within any memory limit. In such cases you must use an adjacency list, which will fit in O(number of edges) memory space. Number of edges can be around 10^5, it still takes up only around 800 KB. (4 bytes per int * 2 vertices per edge * 100000 edges)
2 Likes
