Data Structures with Generic Types in Python/

...

/

AdjacencyMatrix: Representing a Graph by a Matrix

AdjacencyMatrix: Representing a Graph by a Matrix

Learn about the representation of graphs by matrix and lists.

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.

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