Efficient Storage of and Access to Adjacency Lists

Efficient Storage of and Access to Adjacency Lists

Large graphs are stored as adjacency lists to save space. Traditional mechanisms based on arrays of pointers waste space. The following scheme is based on array of indices, which saves space and provides easier access.

Consider a weighted graph, G = (V, E), with |V|= n and |E| = m, where each edge and vertx has a weight.
Below, the two given arrays store all the info necessary to represent the edges of the graph and to facilitate all operations on them efficiently:

 unsigned short xadj[n+1];unsigned short adjncy[m];adjncy[xadj[i]] to adjncy[xadj[i+1]] denote the edges from _vertex i, wherenumber of edges from vetex i = xadj[i+1] - xadj[i]

The weights of vertices and edges can be stored as arrays as follows:

 short edge_wgt[m];short vertex_wgt[n];
See also  10 Best Apps to Help You Read More Books in Less Time

About Our Editorial Process

At DevX, we’re dedicated to tech entrepreneurship. Our team closely follows industry shifts, new products, AI breakthroughs, technology trends, and funding announcements. Articles undergo thorough editing to ensure accuracy and clarity, reflecting DevX’s style and supporting entrepreneurs in the tech sphere.

See our full editorial policy.

About Our Journalist