 # How to store any graph/tree in single dimension array with preprocessing of edges

As we know , we can keep information of graph either by adjacency matrix or adjacency list.
Like in c++ we use vector of list to store graph edges.
But if we store our graph in single dimensional array then it will improve the time complexity as compared to
vector of list [ Really very very fast ].

The main idea to store graph in single array ,is to take cumulative sum of node’s degree count in serial order.

Then start placing [ u - v ] edges in graph array with the help of cumulative sum array of degree
and maintain another copy of the same cumulative sum array of degree.

One copy is used to place the edges into the graph array at their correct position.
Original cumulative sum of degree array is used to traverse the graph.

Space complexity :
One array to store edges [ Size : 2 * E ]
One array used for degree count [ Size : N ]
Copy of degree array count [ Size : N ]
Graph array to store nodes [ Size : 2 * E ]

Overall space complexity : O( 4 * E + 2 * N ) or we can say O(E + V)

Please check the implementation for the above : http://ideone.com/Jb0M9T

I already tested the above the code on 2000000 edges, the time taken to build the graph is almost 1 sec , while for the same graph vector of vector take more than 2.5 sec

2 Likes
//