Adjacency list and matrix in Python using OOP concepts

In this article at OpenGenus, we have implemented Adjacency list and matrix in Python using OOP concepts. This is a must for mastering Graph Algorithm in Python.

Table of Contents

• Introduction
• Adjacency List
• Adjacency Matrix
• Adjacency List Implementation in Python
• Adjacency Matrix Implementation in Python

Introduction:

In graph theory, adjacency lists and adjacency matrices are two common representations of graphs. These representations are used to store and manipulate the relationships between vertices (nodes) in a graph. The choice between adjacency lists and adjacency matrices depends on the specific requirements of the graph operations you need to perform.

Adjacency List:

An adjacency list is a collection of linked lists or arrays, where each element represents a vertex in the graph, and the list or array associated with that vertex contains its adjacent vertices. This representation is particularly useful for sparse graphs, where the number of edges is significantly smaller than the number of vertices.

Adjacency Matrix:

An adjacency matrix is a 2D matrix where each element represents the relationship between two vertices. The rows and columns of the matrix represent the vertices of the graph, and the value in each cell indicates whether an edge exists between the corresponding vertices. This representation is useful for dense graphs, where the number of edges is close to the number of vertices.

Implementing Adjacency List and Matrix using OOP Concepts:

Adjacency List Implementation in Python

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, src, dest):
        self.adj_list[src].append(dest)
        self.adj_list[dest].append(src)

    def display(self):
        for i in range(self.num_vertices):
            print("Adjacency list of vertex {}: ".format(i), end="")
            for j in self.adj_list[i]:
                print("-> {}".format(j), end="")
            print()

#### Example usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.display()

Output:

Adjacency list of vertex 0: -> 1-> 4
Adjacency list of vertex 1: -> 0-> 2-> 3-> 4
Adjacency list of vertex 2: -> 1-> 3
Adjacency list of vertex 3: -> 1-> 2-> 4
Adjacency list of vertex 4: -> 0-> 1-> 3

Here our code sample defines a class called Graph that represents an undirected graph. It provides methods to initialize the graph, add edges between vertices, and display the adjacency list of the graph. class Graph:: defines the class Graph and def __init__(self, num_vertices):: is the constructor method of the Graph class. It initializes a new instance of the class and sets the number of vertices in the graph. The num_vertices parameter is used to determine the size of the adjacency list. self.num_vertices = num_vertices: assigns the value of the num_vertices parameter to the num_vertices attribute of the instance. self.adj_list = [[] for _ in range(num_vertices)]: initializes the adjacency list for the graph and creates an empty list for each vertex in the graph. The list comprehension [[] for _ in range(num_vertices)] creates a list of num_vertices number of empty lists.

def add_edge(self, src, dest):: allows us to add an edge between two vertices. It takes in the source vertex (src) and the destination vertex (dest). It appends the dest vertex to the adjacency list of the src vertex, and vice versa since the graph is undirected. Then def display(self):: is used to display the adjacency list of the graph and iterate over each vertex in the graph and print its adjacency list. for i in range(self.num_vertices):: starts a loop to iterate over the vertices of the graph. print("Adjacency list of vertex {}: ".format(i), end=""): prints the label for the current vertex. for j in self.adj_list[i]:: starts a loop to iterate over each adjacent vertex of the current vertex. and print("-> {}".format(j), end=""): prints the adjacent vertex. print(): prints a newline character to move to the next line after displaying the adjacency list for the current vertex. The example usage demonstrates how to create a graph, add edges between vertices, and display the adjacency list and the output will show the adjacency list for each vertex in the graph.

Adjacency Matrix Implementation in Python

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, src, dest):
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1

    def display(self):
        for row in self.adj_matrix:
            print(row)

#### Example usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.display()

Output:

[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]

Here our code defines a class called "Graph" in Python. This class represents a graph data structure and allows the user to add edges between vertices and display the adjacency matrix of the graph.

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

The Graph class is defined with a constructor method __init__. The constructor takes a parameter num_vertices which specifies the number of vertices in the graph and initializes the instance variable self.num_vertices with the provided value. It also initializes the instance variable self.adj_matrix as a 2D list (matrix) of size num_vertices × num_vertices, filled with zeros.

def add_edge(self, src, dest):
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1

The add_edge method allows adding an edge between two vertices in the graph. It takes two parameters, src (source vertex) and dest (destination vertex) and updates the adjacency matrix by setting the value at src row and dest column to 1, indicating the existence of an edge. It also sets the value at dest row and src column to 1, as the graph is undirected.

def display(self):
        for row in self.adj_matrix:
            print(row)

The display method prints the adjacency matrix of the graph.
It iterates over each row in the adj_matrix and prints the row. The example usage code demonstrates how to create a graph, add edges between vertices, and display the resulting adjacency matrix:

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.display()

This creates an instance of the Graph class called g with 5 vertices. It adds multiple edges using the add_edge method to connect different vertices and calls the display method to print the adjacency matrix of the graph.