Data Structures with Generic Types in Python/

...

/

AdjacencyLists: A Graph as a Collection of Lists

AdjacencyLists: A Graph as a Collection of 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\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 ...