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

AdjacencyMatrix: Representing a Graph by a Matrix

Explore how to represent graphs with adjacency matrices in Python. Understand constant-time implementations for edge manipulation, the trade-offs in memory usage, and how matrix operations reveal graph properties like paths of length two.

We'll cover the following...

An adjacency matrix is a way of representing an n vertex graph G=(V,E)G = (V ,E) by an n×nn \times n matrix, a, whose entries are boolean values.

Python 3.10.4
class AdjacencyMatrix(object):

    def __init__(self, n):

        self.n = n

        self._initialize()

                

    def _initialize(self):

        self.a = new_boolean_matrix(self.n, self.n)

The matrix entry a[i][j] is defined as

a[i][j]={true   if (i,j)∈Efalse   otherwise a[i][j] = \begin{cases} true & \ \ \ \text{if $(i,j)\in E$} \\ false & \ \ \ \text{otherwise} \end{cases}\ ...