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

AdjacencyLists: A Graph as a Collection of Lists

Explore the adjacency list representation of graphs where each vertex tracks its adjacent vertices using list collections. Understand implementation choices, constant time edge additions, and trade-offs in performance for operations like removing or checking edges, and edge traversal. Learn to create and manipulate adjacency list graphs for efficient graph processing.

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\in E.

Visual demonstration of the adjacency list

The visual demonstration of the adjacency list is shown below:

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

The constructor for creating an AdjacencyLists is:

Python 3.10.4
class AdjacencyLists(object):

    def __init__(self, n):

        self.n = n

        self._initialize()

        

    def _initialize(self):

        self.adj = new_array(self.n)

        for i in range(self.n):

            self.adj[i] = ArrayStack()

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 also possible. Specifically, we could have implemented adj as a DLList ...