Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Java

AdjacencyLists: A Graph as a Collection of Lists

Explore the adjacency list representation of graphs in Java to efficiently manage vertices and edges. Understand core operations like addEdge, removeEdge, and hasEdge, and analyze their time complexities. Learn different implementation options and trade-offs for optimizing graph performance.

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:

A graph and its adjacency lists
A graph and its adjacency lists

The code for creating AdjacencyLists is:

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