Data Structures with Generic Types in Java/

...

/

AdjacencyLists: A Graph as a Collection of Lists

AdjacencyLists: A Graph as a Collection of Lists

Learn about the representation of graphs by adjacency 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 list adj[i] contains a list of all the vertices adjacent to vertex i. That is, it contains every index jj such that (i,j)∈E(i,j)\in E.

Visual demonstration of the adjacency lists

The visual demonstration of the adjacency lists is shown below:

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

The code for creating AdjacencyLists is:

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 ...