Implementation of Graph in Python

Implementation of Graph in Python - Using Adjacency Matrix

A graph can be represented using an adjacency Matrix. An adjacency matrix is a square matrix of size V * V, where V is the number of vertices in the graph. The values in the matrix show whether a given pair of nodes are adjacent to each other in the graph structure or not. In the adjacency matrix, 1 represents an edge from node X to node Y, while 0 represents no edge from X to Y.

The adjacency matrix representation of the above-directed graph is:

Note that for an undirected graph, the adjacency matrix is always symmetric. For a weighted graph, instead of 0 and 1, the value of weight w is used to indicate that there is an edge from i to j.

Implementation

The Implementation of Graphs in Python using Adjacency Matrix is done in the following program:

• Python

Python

# Adjacency Matrix representation of a graph
class Graph:
    # self represents the instance of the class. 
    # By using the “self” keyword we can access the 
    # attributes and methods of the class in python.
    # It binds the attributes with the given arguments.

    # This constructor is used to initialize the adjacecny matrix
    # with 0.
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                            for row in range(vertices)]
    

    # This function prints the adjacency matrix of the graph
    # Due to two nested loops, it is O(V^2)
    def printGraph(self):
        print("\nAdjacency Matrix:")
        for i in range(self.V):
            for j in range(self.V):
                print(self.graph[i][j], end = " ")
            print()
    
    # This function is used to add an edge
    # between vertices v and w.
    # This implementation is for undirected graph
    def addEdge(self, v, w):
        print("Adding an edge between", v , "and", w , "and between", w , "and", v)
        self.graph[v][w] = 1
        self.graph[w][v] = 1
    

    # This function is used to add a
    # vertex to the graph.
    def addVertex(self, v):
        self.V += 1
        for i in range(self.V-1):
            self.graph[i].append(0)
        self.graph.append([0 for column in range(self.V)])
    

if __name__ == "__main__":

    # Initialize the graph with 5 vertices
    g = Graph(5)

    # An edge between 0 and 1 and between 1 and 0 will be created
    g.addEdge(0, 1)

    # An edge between 0 and 2 and between 2 and 0 will be created
    g.addEdge(0, 2)

    # An edge between 1 and 2 and between 2 and 1 will be created
    g.addEdge(1, 2)

    # An edge between 2 and 0 and between 2 and 0 will be created
    g.addEdge(2, 0)

    # An edge between 2 and 3 and between 3 and 2 will be created
    g.addEdge(2, 3)

    # An edge between 3 and 4 and between 4 and 3 will be created
    g.addEdge(3, 4)
    g.printGraph()

You can also try this code with Online Python Compiler

Run Code

The output of the above program is:

Adding an edge between 0 and 1 and between 1 and 0
Adding an edge between 0 and 2 and between 2 and 0
Adding an edge between 1 and 2 and between 2 and 1
Adding an edge between 2 and 0 and between 0 and 2
Adding an edge between 2 and 3 and between 3 and 2
Adding an edge between 3 and 4 and between 4 and 3

Adjacency Matrix:
0 1 1 0 0 
1 0 1 0 0 
1 1 0 1 0 
0 0 1 0 1 
0 0 0 1 0 

The time complexity of the addEdge() function is O(1) and the space complexity is O(V^2).

Advantages of Adjacency Matrix Representation 

The advantages of adjacency Matrix representation are as follows:

• Insertion and deletion of an edge can be done in O(1) time.
• We can easily determine if two edges are adjacent to each other in constant time complexity.

Disadvantages of Adjacency Matrix Representation 

The major disadvantage of Adjacency Matrix Representation is as follows:

• The memory consumption of adjacency matrix representation is of the order of O(V^2), where V is the number of vertices in the graph, which is way too high as compared to Adjacency Lists
• Traversal of a graph requires O(V^2) time complexity.

Implementation of Graph in Python- Using Adjacency List

A graph can also be represented in the form of an adjacency list. An adjacency list represents a graph as an array of linked lists, wherein the index of the array represents a vertex, and each element of the linked list represents other vertices that form an edge with the vertex.

The adjacency list representation of the above graph is:

In the adjacency list representation shown above, the vertices A, B, C, D, and E will be stored in a list, and each vertex will have a separate list containing the vertices that form an edge with the vertex.

Implementation

The below program shows the implementation of Graphs in Python using adjacency list representation. 
 

• Python

Python

# A utility function to add a vertex to the graph                      
''' 
     The purpose of using global variables inside all the 
     functions defined below is that global variables can be 
     used both inside and outside the functions
'''


def addVertex(vertex):
    global graph

    # This variable is used to count the number of vertices in the graph
    global vertexCount

    # If the vertex already exists in the graph
    if vertex in graph:
        print("Vertex ", vertex, " already exists in the graph ")

    # Otherwise create a new list for this vertex and increase the count of
    # vertices in the vertexCount variable
    else:
        vertexCount += 1
        graph[vertex] = []


# A utility function to add an edge between
# vertex source and destination

def addEdge(source, destination):
    global graph

    # Check if the source vertex exists in the graph
    if source not in the graph:
        print("Source vertex ", source, " does not exist in the graph")

    # Check if the destination vertex exists in the graph
    elif destination not in graph:
        print("Destination vertex ", destination,
              " do not exist in the graph")

    # If both the source and destination vertex exists in the
    # graph, an edge can be added.
    else:
        
        # Create a new list by passing in the data of the destination vertex
        temp = [destination]

        # The append() method adds a single item to the list. A new list is
        # not created. Instead, the original list is modified by adding the new
        # item to the rear of the original list
        graph[source].append(temp)


# A utility function to print the adjacency list representation of
# a graph
def printGraph():
    global graph

    # Pick each vertex
    for vertex in graph:
    # Pick all the vertices that form an edge with the picked vertex above.
        for edges in graph[vertex]:
            print(vertex, "->", edges[0])


if __name__ == '__main__':

    # Initializing the graph with an empty list
    # This will store all the vertices
    graph = {}

    # This variable is used to store the count of vertices in the graph
    vertexCount = 0

    # Creating 5 vertices in the graph. Initially none
    # of them is connected to each other or have an edge
    # between them
    addVertex(1)
    addVertex(2)
    addVertex(3)
    addVertex(4)
    addVertex(5)
    # Adding the edges between source and destination vertices
    addEdge(1, 2)
    '''
    1 --------> 2
    '''

    addEdge(2, 3)
    '''
    1 ---------> 2
                 |
                 |
                \|/
                 3
    '''

    addEdge(3, 4)
    '''
    1 ----------> 2
                  |
                  |
                 \|/
    4 <---------- 3
    '''

    addEdge(4, 1)
    '''
    1 ----------> 2
   /|\            |
    |             |
    |            \|/
    4 <---------- 3
    '''

    # Function call to printGraph() function 
    printGraph()
    print("Internal representation of graph is: ", graph)

You can also try this code with Online Python Compiler

Run Code

The output of the above program is:

1 -> 2
2 -> 3
3 -> 4
4 -> 1
Internal representation of graph is:  {1: [[2]], 2: [[3]], 3: [[4]], 4: [[1]], 5: []}

The time complexity of the addVertex() is O(1), addEdge() is O(1) as append() operation takes constant time. The printGraph() function however takes O(V*E) time. 

The space complexity of the above program is O(V + E), where V is the number of vertices and E is the number of edges. The space complexity of the above program will be O(V^2) in the case of a complete graph.

Must Read Difference between ArrayList and LinkedList

Advantages of Adjacency List representation

The advantages of adjacency Matrix representation are as follows:

• The representation is quite easy to follow and implement. It clearly shows the adjacent nodes of a particular node.
• For graphs with a small-to-moderate number of edges, the Adjacency list consumes less memory of the order of [O(V + E), where V is the number of vertices and E is the number of edges] as compared to the Adjacency matrix. Therefore it is a preferred choice for a graph with a small-to-moderate number of nodes.

Disadvantages of Adjacency List representation

The disadvantages of adjacency Matrix representation are:

• It takes linear time to determine whether there is an edge from vertex ‘i’ to ‘j’ as compared to the constant time in the case of the adjacency matrix.  
• Also, in the case of graphs with a high number of vertices and edges, the memory consumption O(V^2) is comparable to the Adjacency Matrix. So the adjacency matrix is a preferred choice in such cases.

Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

How is the graph implemented?

Graphs can be implemented using adjacency lists or adjacency matrices. An adjacency list uses a dictionary of lists to represent edges, while an adjacency matrix uses a 2D array to indicate connections between vertices.

Which Libraries Can Be Used for Graph Implementation in Python?

Several libraries facilitate graph implementation in Python, including NetworkX, which provides tools for creating, manipulating, and analyzing complex networks, and Graph-tool, which offers efficient graph algorithms and visualization capabilities for large graphs.

How Do You Implement Depth-First Search (DFS) in a Python Graph?

Depth-First Search (DFS) can be implemented using recursion or a stack. Starting from a given node, the algorithm explores as far as possible along each branch before backtracking, marking visited nodes to avoid cycles.

How is a graph traversed?

Traversal of a graph means visiting all the vertices and edges of the graph. Graph traversal can be done in one of the following ways. 

1. Breadth-First Search
2. Depth First Search.

Conclusion

Graphs are one of the most important data structures from an interview perspective in product-based companies. This article discusses the implementation of Graph in Python. 

Recommended Readings:

• Graph using STL
• Implementation of Graph in Java
• Graph Theory
• Graph Types and Applications
• Properties of Graph
• Fibonacci Series in Python