In this article, we will learn how to represent a graph using Linked Lists. A graph is a data structure that consists of a set of vertices (nodes) and a set of pairs showing the connection between vertices. A single pair is known as an edge. Moreover, if the graph is directed, then it will be ordered. For example,
(v1, v2) shows that a connection line exists from v1 to v2 and not from v2 to v1. On the contrary, if the graph is undirected, then we have unordered pairs. For example,
(v1, v2) shows that an edge exists from v1 to v2 and v2 to v1.
You can represent a graph using an Adjacency List. The Adjancey list is an array of linked lists, where the array length is equal to the number of vertices, and each array index represents a node. Moreover, an array item at index
i contains a linked list containing all nodes adjacent to vertex
Implementation of Graph Representation using Linked List
This implementation of graphs using linked lists has the following functionalities:
- Creation: The graph can either be a Directed or an Undirected Graph. By default, it is directed.
- Insert an edge: It takes a pair
(v1, v2)and adds it to the graph. If it is a directed graph, we only add v2 in the linked list of vertex v1 located at index v1. Otherwise, we also insert an edge from v2 to v1.
- Display the graph: It shows the complete graph represented using linked lists.
The code is given below.
class Node: def __init__(self,vertex=None): self.vertex = vertex self.next = None #implementation of linked list for the graph class LinkedList: def __init__(self): self.head = None #add a vertex in the linked list def insert(self, vertex): node = Node(vertex) #create a node if self.head == None: #if list is empty insert a vertex(node) at the start self.head = node else: temp = self.head #iterate through the list till last node is found while temp.next: temp = temp.next temp.next = node #adding a new node #traverse through a linked list def traverse(self): temp = self.head while temp: print(temp.vertex, end='-->') temp = temp.next #representation of graph using linked lists class Graph: def __init__(self, no_vertices, directed=True): self.no_vertices = no_vertices self.vertices_list = [LinkedList() for i in range(0, no_vertices)] #create a list to represent the graph self.directed = directed #insert an edge in the graph def insert_edge(self, edge): vertex1, vertex2 = edge if (vertex1 >=0 and vertex1 < self.no_vertices) and (vertex2 >=0 and vertex2 < self.no_vertices): #add an edge from vertex1 to vertex2 self.vertices_list[vertex1].insert(vertex2) if not self.directed: #if the graph is undirected, add an edge from vertex2 to vertex1 as well self.vertices_list[vertex2].insert(vertex1) else: raise ValueError("Invalid vertices") #display the graph def display_graph(self): for i in range(0, self.no_vertices): print(i, end="\t") self.vertices_list[i].traverse() print("None")
Create an undirect Graph
Now call the function above to create an Undirect Graph:
n = 5 #number of vertices graph = Graph(n, directed=False) #create an undirected graph #insert edges graph.insert_edge((0, 3)) graph.insert_edge((1, 3)) graph.insert_edge((1, 2)) graph.insert_edge((2, 4)) graph.insert_edge((3, 4)) #display graph graph.display_graph()
0 3-->None 1 3-->2-->None 2 1-->4-->None 3 0-->1-->4-->None 4 2-->3-->None
Create a Direct Graph
Again, call the function to create a direct Graph
n = 5 #number of vertices graph = Graph(n, directed=True) #create a directed graph #insert edges graph.insert_edge((0, 3)) graph.insert_edge((2, 1)) graph.insert_edge((2, 4)) graph.insert_edge((3, 1)) graph.insert_edge((3, 4)) graph.insert_edge((4, 2)) #display graph graph.display_graph()
0 3-->None 1 None 2 1-->4-->None 3 1-->4-->None 4 2-->None