Data Structures with Generic Types in C++/

...

/

AdjacencyLists: A Graph as a Collection of Lists

AdjacencyLists: A Graph as a Collection of Lists

Learn about the representation of graphs by lists.

We'll cover the following...

Adjacency list representations of graphs take a more vertex-centric approach. There are many possible implementations of adjacency lists. In this section, we present a simple one. At the end of the section, we discuss different possibilities. In an adjacency list representation, the graph G=(V,E)G = (V,E) is represented as an array, adj, of lists. The adj[i] list contains a list of all the vertices adjacent to vertex i. That is, it contains every index jj such that (i,j) ∈E\in E.

Visual demonstration of the adjacency list

The visual demonstration of the adjacency list is shown below:

Press + to interact
A graph and its adjacency lists
A graph and its adjacency lists

The constructor for creating an AdjacencyLists is as follows:

Press + to interact
int n;

List < Integer > [] adj;

AdjacencyLists(int n0) {

  n = n0;

  adj = (List < Integer > []) new List[n];

  for (int i = 0; i < n; i++)

    adj[i] = new ArrayStack < Integer > ();

}

In this particular implementation, we represent each list in adj as an ArrayStack, because we would like constant time access by position. Other options are ...