Introduction of Graph

Graph:- It is a non-linear data structure. A graph G consist of a non empty set V where members are called the vertices of graph and the set E where member are called the edges.

G = (V, E)

V = set of vertices

E = set of edges

Example:-

G = (V, E)

V = {A,B,C,D,E}

E = {e1,e2,e3,e4,e5} or {(A,B), (A,C), (B,C), (C,D), (C,E)}

 

---

 

Basic Terminology of Graph

Vertex (or node):

A vertex or node is a fundamental unit in a graph. In a simple graph, each vertex can be connected to other vertices by edges. Vertices are often represented by circles or dots in visual representations of graphs.

 

Edge:

An edge is a line or connection between two vertices in a graph. Edges can be directed or undirected, and weighted or unweighted. In an undirected graph, edges connect vertices without a specified direction, while in a directed graph, edges have a direction, represented by an arrow. In a weighted graph, edges have a numerical weight or value assigned to them.

 

Degree:

The degree of a vertex is the number of edges that are connected to it. In a directed graph, the degree of a vertex is defined as the sum of the in-degree (number of edges coming into the vertex) and out-degree (number of edges going out of the vertex).

 

Path:

A path is a sequence of vertices connected by edges. A simple path is a path where no vertex is repeated.

 

Cycle:

A cycle is a path that starts and ends at the same vertex.

 

Connectedness:

A graph is said to be connected if there is a path between any two vertices in the graph. A disconnected graph is a graph that is not connected, meaning it can be broken into two or more separate components.

 

Component:

A component is a connected subgraph of a larger graph. In other words, it is a part of the graph that is connected to other vertices or edges within that part, but not connected to the rest of the graph.

 

Directed graph:

A directed graph is a graph where edges have a direction, represented by an arrow. In a directed graph, edges are often called arcs.

 

Undirected graph:

An undirected graph is a graph where edges do not have a direction.

 

Weighted graph:

A weighted graph is a graph where edges have weights or values assigned to them.

 

Adjacent vertices:

Two vertices are adjacent if they are connected by an edge.

 

Incidence:

A vertex is incident on an edge if the vertex is one of the endpoints of the edge.

 

Subgraph:

A subgraph is a graph that is a subset of another graph, with some edges and vertices removed.

 

Complete graph:

A complete graph is a graph where every vertex is connected to every other vertex. In other words, there is an edge between every pair of vertices in the graph.

 

Logical Representation of graph

 

---

 

Graph Representation in data structure

Adjacency matrix:

An adjacency matrix is a two-dimensional array or list that represents a graph. The matrix has a row and column for each vertex, and the value at position (i, j) indicates whether there is an edge between vertices i and j. If there is an edge, the value is 1, and if there is no edge, the value is 0. This representation is useful for dense graphs, where the number of edges is close to the maximum possible number of edges. In python we can use NumPy array or python list for adjacency matrix.

.

Adjacency list:

An adjacency list is a list of lists where each vertex has a list of its adjacent vertices. Each list contains the vertices that are adjacent to the vertex at that index. This representation is useful for sparse graphs, where the number of edges is much smaller than the maximum possible number of edges. In python we can use dictionary for adjacency list.

 

For unweighted directed graph

 

G = (V, E)

V = [0,1,2,3,4]

E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]

 

Adjacency matrix representation:

Using NumPy 2d array

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)] # each tuple(u,v) represent edge from u to v
size = len(V)
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in E:
    AMat[i,j] = 1 # mark 1 if edge present in graph from i to j , otherwise 0
print(AMat)

Output adjacency matrix (AMat)

[[0. 1. 1. 0. 0.]
    [0. 0. 0. 1. 1.]
    [0. 0. 0. 1. 1.]
    [0. 0. 0. 0. 1.]
    [0. 0. 0. 0. 0.]]
# AMat[i,j] == 1 represent edge from i to j 

 

Using Python nested list

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]
size = len(V)
AMat = []
for i in range(size):
    row = []
    for j in range(size):
        row.append(0)
    AMat.append(row.copy())       
for (i,j) in E:
    AMat[i][j] = 1 # mark 1 if edge present in graph from i to j , otherwise 0
print(AMat)

Output adjacency matrix (AMat)

[[0, 1, 1, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]
# AMat[i][j] == 1 represent edge from i to j

 

Adjacency list representation:

Using python dictionary

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]
size = len(V)
AList = {}
# In dictionay AList, for example, AList[i] = [j,k] represent two edge from i to j and i to k
for i in range(size):
    AList[i] = []
for (i,j) in E:
    AList[i].append(j)
print(AList)

Output adjacency list (AList)

{0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
# for example, AList[i] = [j,k] represent two edge from i to j and i to k

 

For unweighted undirected graph

G = (V, E)

V = [0,1,2,3,4]

E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]

 

Adjacency matrix representation:

Using NumPy 2d array

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]
UE = E + [ (j,i) for (i,j) in E] # each edge represented by two tuple (u,v) and (v,u)
size = len(V)
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in UE:
    AMat[i,j] = 1 # mark 1 if edge present in graph from i to j , otherwise 0
print(AMat)

Output adjacency matrix (AMat)

[[0. 1. 1. 0. 0.]
    [1. 0. 0. 1. 1.]
    [1. 0. 0. 1. 1.]
    [0. 1. 1. 0. 1.]
    [0. 1. 1. 1. 0.]]
    # AMat[i,j] == 1 represent edge from i to j

 

Using Python nested list

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]
UE = E + [ (j,i) for (i,j) in E] # each edge represented by two tuple (u,v) and (v,u)
size = len(V)
AMat = []
for i in range(size):
    row = []
    for j in range(size):
        row.append(0)
    AMat.append(row.copy())       
for (i,j) in UE:
    AMat[i][j] = 1 # mark 1 if edge present in graph from i to j , otherwise 0
print(AMat)

Output adjacency matrix (AMat)

[[0, 1, 1, 0, 0], 
[1, 0, 0, 1, 1], 
[1, 0, 0, 1, 1], 
[0, 1, 1, 0, 1], 
[0, 1, 1, 1, 0]]
# AMat[i][j] == 1 represent edge from i to j

 

Adjacency list representation:

Using python dictionary

V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)]
UE = E + [ (j,i) for (i,j) in E] # each edge represented by two tuple (u,v) and (v,u)
size = len(V)
AList = {}
# In dictionay AList, for example, AList[i] = [j,k] represent two edge from i to j and i to k
for i in range(size):
    AList[i] = []
for (i,j) in UE:
    AList[i].append(j)
print(AList)

Output adjacency list (AList)

{0: [1, 2], 1: [3, 4, 0], 2: [4, 3, 0], 3: [4, 1, 2], 4: [1, 2, 3]}
# for example, AList[i] = [j,k] represent two edge from i to j and i to k

 

---

 

Graph Traversing Algorithm

Graph traversal is the process of visiting all the vertices (nodes) of a graph. There are two commonly used algorithms for graph traversal:

1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)

 

Breadth First Search(BFS)

The Breadth First Search (BFS) algorithm is used to traverse a graph or a tree in a breadth-first manner. BFS starts at the root node and explores all the neighboring nodes at the current depth before moving on to the nodes at the next depth. This is done by using a queue data structure. The algorithm marks each visited node to avoid revisiting it.

Algorithm

Here are the steps for the BFS algorithm:

1. Choose a starting node and enqueue it to a queue.
2. Mark the starting node as visited.
3. While the queue is not empty, dequeue a node from the front of the queue.
4. For each of the dequeued node's neighbors that are not visited, mark them as visited and enqueue them to the queue.
5. Repeat steps 3-4 until the queue is empty.

To keep track of the traversal order, you can add each visited node to a list as it is dequeued from the queue.

 

Complexity is $O(V^2 )$ using adjacency matrix, $O(V + E)$ using adjacency list, Where $V$ is number of vertices and $E$ is number of edges in Graph.

 

Working Visualization

 

Implementation BFS for adjacency list of graph

# Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])    
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# BFS Implementation For Adjacency list
def BFSList(AList,start_vertex):
    # Initialization
    visited = {}
    for each_vertex in AList.keys():
        visited[each_vertex] = False    
    
    # Create Queue object q
    q = Queue()
    
    # Mark the start_vertex visited and insert it into the queue 
    visited[start_vertex] = True
    q.enqueue(start_vertex)
    
    # Repeat the following until the queue is empty 
    while(not q.isempty()):
        # Remove the one vertex from queue
        curr_vertex = q.dequeue()
        # Visit each adjacent of the removed vertex (if not visited), mark that visited, and insert it into the queue 
        for adj_vertex in AList[curr_vertex]:
            if (not visited[adj_vertex]):
                visited[adj_vertex] = True
                q.enqueue(adj_vertex)               
    return(visited)

AList = {0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
print(BFSList(AList,0))

Output

{0: True, 1: True, 2: True, 3: True, 4: True}

 

Code Execution Flow

 

Implementation BFS for adjacency matrix of graph

# Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# Function to return list of neighbours or adjacent vertex of vertex i
def neighbours(AMat,i):
    nbrs = []
    (rows,cols) = AMat.shape
    for j in range(cols):
        if AMat[i,j] == 1:
            nbrs.append(j)
    return(nbrs)

# BFS Implementation For Adjacency matrix
def BFS(AMat,start_vertex):
    # Initialization
    (rows,cols) = AMat.shape
    visited = {}
    for each_vertex in range(rows):
        visited[each_vertex] = False    
    
    # Create Queue object q
    q = Queue()
    
    # Mark the start_vertex visited and insert it into the queue 
    visited[start_vertex] = True
    q.enqueue(start_vertex)
    
    # Repeat the following until the queue is empty 
    while(not q.isempty()):
        # Remove the one vertex from queue
        curr_vertex = q.dequeue()
        # Visit the each adjacent of removed vertex(if not visited) and insert into the queue
        for adj_vertex in neighbours(AMat,curr_vertex):
            if (not visited[adj_vertex]):
                visited[adj_vertex] = True
                q.enqueue(adj_vertex)
                
    return(visited)


V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)] 
size = len(V)
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in E:
    AMat[i,j] = 1
print(BFS(AMat,0))

Output

{0: True, 1: True, 2: True, 3: True, 4: True}

 

Code Execution Flow

 

 

Find parent of each vertex using BFS

Parent information is useful to determine shortest path from vertex v in term of number of edges or vertex in path.

# Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# Using BFS approch For Adjacency list, for path, maintaining the parent of each vertex
# Path can be found by backtracking from destination to source using parent information
def BFSListPath(AList,start_vertex):
    # Initialization
    (visited,parent) = ({},{})
    for each_vertex in AList.keys():
        visited[each_vertex] = False
        parent[each_vertex] = -1   
    
    # Create Queue object q
    q = Queue()
    
    # Mark the start_vertex visited and insert it into the queue 
    visited[start_vertex] = True
    q.enqueue(start_vertex)
    
    # Repeat the following until the queue is empty
    while(not q.isempty()):
        # Remove the one vertex from queue
        curr_vertex = q.dequeue()
        # Visit the each adjacent of removed vertex(if not visited) and insert into the queue
        for adj_vertex in AList[curr_vertex]:
            if (not visited[adj_vertex]):
                visited[adj_vertex] = True
                # Assigne the curr_vertex as parent of each unvisited adjacent of curr_vertex
                parent[adj_vertex] = curr_vertex
                q.enqueue(adj_vertex)
                
    return(visited,parent)


AList ={0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
print(BFSListPath(AList,0))

Output

({0: True, 1: True, 2: True, 3: True, 4: True}, {0: -1, 1: 0, 2: 0, 3: 1, 4: 1})

 

 

Find level number of vertices using BFS

Maintain level information to record length of the shortest path, in terms of number of edges or vertex.

# Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# Using BFS approch For Adjacency list, for path, maintaining the parent of each vertex
# Using BFS approch maintaing the adjacent level number from source vertrex
def BFSListPathLevel(AList,v):
    # Initialization
    (level,parent) = ({},{})
    for each_vertex in AList.keys():
        level[each_vertex] = -1
        parent[each_vertex] = -1
    
    # Create Queue object q
    q = Queue()
    
    # Assigning the level 0 for start_vertex and insert it into the queue
    level[v] = 0
    q.enqueue(v)
    
    # Repeat the following until the queue is empty
    while(not q.isempty()):
        # Remove the one vertex from queue
        curr_vertex = q.dequeue()
        # Visit the each adjacent of curr_vertex(if level value is -1) and insert into the queue
        for adj_vertex in AList[curr_vertex]:
            if (level[adj_vertex] == -1):
                # Assign the level value on each adjacent one more than the curr_vertex level
                level[adj_vertex] = level[curr_vertex] + 1
                # Assigne the curr_vertex as parent of adjacent vertex of curr_vertex
                parent[adj_vertex] = curr_vertex
                q.enqueue(adj_vertex)
                
    return(level,parent)


AList ={0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
print(BFSListPathLevel(AList,0))

Output

({0: 0, 1: 1, 2: 1, 3: 2, 4: 2}, {0: -1, 1: 0, 2: 0, 3: 1, 4: 1})

 

---

 

Depth First Search(DFS)

The Depth First Search (DFS) algorithm is used to traverse a graph or a tree in a depth-first manner, exploring as far as possible along each branch before backtracking. This is done by using a stack data structure.

 

Algorithm

Here are the steps for the Recursive DFS algorithm:

1. Choose a starting node and mark it as visited.
2. For each unvisited neighbor of the starting node, recursively call the DFS algorithm starting from that neighbor.
3. Repeat step 2 for all unvisited neighbors.

 

Here are the steps for DFS using a stack:

1. Create a stack S and a set visited to keep track of visited nodes.

2. Push the starting node onto the stack S.

3. While S is not empty, pop the top element u from S.

4. If u is not visited, mark it as visited and do the following:

   • Perform any processing on the node u.
   • Get all unvisited neighbors v of u and push them onto S.

5. Repeat steps 3-4 until S is empty.

To keep track of the traversal order, you can add each visited node to a list as it is visited.

 

Complexity is $O(V^2 )$ using adjacency matrix, $O(V + E)$ using adjacency list, Where $V$ is number of vertices and $E$ is number of edges in Graph.

 

Working Visualization

 

Implementation of DFS for adjacency list of graph

DFS using Stack for adjacency list of graph

# Stack Implementation
class Stack:
    def __init__(self):
        self.stack = []
    def Push(self,v):
        self.stack.append(v)
    def isempty(self):
        return(self.stack == [])
    def Pop(self):
        v = None
        if not self.isempty():
            v = self.stack.pop()
        return(v)    
    def __str__(self):
        return(str(self.stack))

# DFS Implementation for Adjacency list
def DFSList(AList,start_vertex):
    # Initializaion
    visited = {}
    for each_vertex in AList.keys():
        visited[each_vertex] = False    
    
    # Create stack object st
    st = Stack()
    
    # Push start_vertex in to the stack as first vertex
    st.Push(start_vertex)    
    
    # Repeat the following until the stack is empty
    while(not st.isempty()):
        # Pop one vertex from stack 
        current_vertex = st.Pop()
        # If popped vertex is not visited, marked visited
        if visited[current_vertex] == False:
            visited[current_vertex] = True
            # Push all unvisited adjacent of popped vertex into the stack
            for adj_veretx in AList[current_vertex]:
                    if(not visited[adj_veretx]):
                        st.Push(adj_veretx)    
    return(visited)


AList ={0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
print(DFSList(AList,0))

Output

{0: True, 1: True, 2: True, 3: True, 4: True}

 

Code Execution Flow

 

DFS Recursive (without using external stack)

# Initialization Function
def DFSInitList(AList):
    (visited,parent) = ({},{})
    for each_vertex in AList.keys():
        visited[each_vertex] = False
        parent[each_vertex] = -1
    return(visited,parent)

# DFS Recursive Implementation for Adjacency list
def DFSList(AList,visited,parent,v):
    # Mark vertex v as visited vertex
    visited[v] = True
    # Repeat following for each unvisited adjacent of vertex v
    for adj_vertex in AList[v]:
        if (not visited[adj_vertex]):
            # Assign vertex v as parent of each unvisited adjacent of v 
            parent[adj_vertex] = v
            
            # Recursively call the DFS on unvisited adjacent of v
            (visited,parent) = DFSList(AList,visited,parent,adj_vertex)
            
    return(visited,parent)


AList ={0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
v,p = DFSInitList(AList)
print(DFSList(AList,v,p,0))

Output

({0: True, 1: True, 2: True, 3: True, 4: True}, {0: -1, 1: 0, 2: 0, 3: 1, 4: 3})

 

Code Execution Flow

 

DFS global for adjacency list of graph

# Global variable
(visited,parent) = ({},{})

# Initialization function
def DFSInitListGlobal(AList):   
    for each_vertex in AList.keys():
        visited[each_vertex] = False
        parent[each_vertex] = -1
    return

# DFS Recursive Implementation for Adjacency list
def DFSListGlobal(AList,v):
    # Mark vertex v as visited vertex
    visited[v] = True
    # Repeat following for each unvisited adjacent of vertex v
    for adj_vertex in AList[v]:
        if (not visited[adj_vertex]):
            # Assign vertex v as parent of each unvisited adjacent of v 
            parent[adj_vertex] = v
            # Recursively call the DFS on unvisited adjacent of v
            DFSListGlobal(AList,adj_vertex)                
    return


AList ={0: [1, 2], 1: [3, 4], 2: [4, 3], 3: [4], 4: []}
DFSInitListGlobal(AList)
DFSListGlobal(AList,0)
print(visited,parent)

Output

{0: True, 1: True, 2: True, 3: True, 4: True} {0: -1, 1: 0, 2: 0, 3: 1, 4: 3}

 

Implementation of DFS for adjacency matrix of graph

# Function to return list of neighbours or adjacent vertex of vertex i
def neighbours(AMat,i):
    nbrs = []
    (rows,cols) = AMat.shape
    for j in range(cols):
        if AMat[i,j] == 1:
            nbrs.append(j)
    return(nbrs)

# Initialization Function
def DFSInit(AMat):
    (rows,cols) = AMat.shape
    (visited,parent) = ({},{})
    for each_vertex in range(rows):
        visited[each_vertex] = False
        parent[each_vertex] = -1
    return(visited,parent)

# DFS Recursive Implementation for Adjacency matrix
def DFS(AMat,visited,parent,v):
    # Mark vertex v as visited vertex
    visited[v] = True
    # Repeat following for each unvisited adjacent of vertex v
    for adj_vertex in neighbours(AMat,v):
        if (not visited[adj_vertex]):
            # Assign vertex v as parent of each unvisited adjacent of v 
            parent[adj_vertex] = v
            # Recursively call the DFS on unvisited adjacent of v
            (visited,parent) = DFS(AMat,visited,parent,adj_vertex)
            
    return(visited,parent)


V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)] 
size = len(V)
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in E:
    AMat[i,j] = 1
v,p=DFSInit(AMat)
print(DFS(AMat,v,p,0))

Output

({0: True, 1: True, 2: True, 3: True, 4: True}, {0: -1, 1: 0, 2: 0, 3: 1, 4: 3})

 

Code Execution Flow

 

 

DFS global for adjacency matrix of graph

# Global variables
(visited,parent) = ({},{})

# Function to return list of neighbours or adjacent vertex of vertex i
def neighbours(AMat,i):
    nbrs = []
    (rows,cols) = AMat.shape
    for j in range(cols):
        if AMat[i,j] == 1:
            nbrs.append(j)
    return(nbrs)

# Initialization Function
def DFSInitGlobal(AMat):
    (rows,cols) = AMat.shape    
    for each_vertex in range(rows):
        visited[each_vertex] = False
        parent[each_vertex] = -1
    return

# DFS Recursive Implementation for Adjacency matrix
def DFSGlobal(AMat,v):
    # Mark vertex v as visited vertex
    visited[v] = True
    # Repeat following for each unvisited adjacent of vertex v
    for adj_vertex in neighbours(AMat,v):
        if (not visited[adj_vertex]):
            # Assign vertex v as parent of each unvisited adjacent of v
            parent[adj_vertex] = v
            # Recursively call the DFS on unvisited adjacent of v
            DFSGlobal(AMat,adj_vertex)                
    return


V = [0,1,2,3,4]
E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (2, 3), (3, 4)] 
size = len(V)
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in E:
    AMat[i,j] = 1
DFSInitGlobal(AMat)
DFSGlobal(AMat,0)
print(visited,parent)

Output

{0: True, 1: True, 2: True, 3: True, 4: True} {0: -1, 1: 0, 2: 0, 3: 1, 4: 3}

 

---

 

Application of BFS and DFS

Find Connected Components in graph using BFS

The Connected Components in a Graph using BFS algorithm is used to find all the connected components in an undirected graph.

Algorithm

Here are the steps for the Connected Components in Graph using BFS algorithm:

1. Create a queue and an array visited to keep track of the visited nodes in the graph.
2. Initialize dictionary component[v] = -1 for each vertex v in the graph
3. For each unvisited node u in the graph, perform a BFS traversal starting from u and assign new component id to all the visited nodes as a single connected component in component dictionary.
4. Repeat steps 3 until all nodes in the graph are visited.
5. Return component dictionary.

 

For given graph

 

Implementation of Find Connected Components in graph using BFS

# Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# BFS Implementation for Adjacency list
def BFSList(AList,start_vertex):
    visited = {}
    for each_vertex in AList.keys():
        visited[each_vertex] = False
    
    q = Queue()    
    visited[start_vertex] = True
    q.enqueue(start_vertex)
    
    while(not q.isempty()):
        curr_vertex = q.dequeue()
        for adj_vertex in AList[curr_vertex]:
            if (not visited[adj_vertex]):
                visited[adj_vertex] = True
                q.enqueue(adj_vertex)               
    return(visited)

# Implementation to find connected components in graph
def Components(AList):
    # Initialization of component value -1 for each vertex
    component = {}
    for each_vertex in AList.keys():
        component[each_vertex] = -1   
    
    # Initialize compid(represent conntected component id)
    # Initialize seen(represent number of visited/checked vertices)
    (compid,seen) = (0,0)
    
    # Repeat the following untill seen value is not equal to number of vertex
    while seen < max(AList.keys()):
        # Find the min level value vertex among all vertices which are not checked or visited
        startv = min([i for i in AList.keys() if component[i] == -1])
        # Call the BFS to check the reachability from startv
        visited = BFSList(AList,startv)  
        # Assign compid value to each reachable vertex from startv and increment seen value
        for vertex in visited.keys():
            if visited[vertex]:
                seen = seen + 1
                component[vertex] = compid
        
        # Increment compid by one to check again if any vertex are remaing to visisted 
        compid = compid + 1  
    
    return(component)


AList = {0: [1], 1: [2], 2: [0], 3: [4, 6], 4: [3, 7], 5: [3, 7], 6: [5], 7: [4, 8], 8: [5, 9], 9: [8]}
print(Components(AList))

Output

{0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1}

 

 

Pre and Post numbering using DFS

The Pre and Post numbering using DFS algorithm is used to assign a unique number to each node in a graph during a Depth-First Search (DFS) traversal.

Algorithm

Here are the steps for the Pre and Post numbering using DFS algorithm:

1. Initialize a counter count to 0 and two dictionary pre and post to keep track of the pre and post numbers of the nodes.
2. For each unvisited node u in the graph, perform a DFS traversal starting from u.
3. During the DFS traversal, visit each unvisited neighbor v of the current node u and recursively perform a DFS traversal starting from v.
4. Increment the count and assign it as the pre number of the current node u.
5. After all neighbors of the current node u have been visited, increment the count again and assign it as the post number of the current node u.
6. Repeat steps 3-5 until all nodes in the graph are visited.
7. Return the pre and post arrays.

 

For given graph

Implementation of Pre and Post numbering on graph using DFS

# Global variables
(visited,pre,post) = ({},{},{})

# Initialization
def DFSInitPrePost(AList):   
    for each_vertex in AList.keys():
        visited[each_vertex] = False
        (pre[each_vertex],post[each_vertex]) = (-1,-1)
    return

# Implementation of Pre and Post numbering on graph using DFS approch
def DFSListPrePost(AList,v,count):
    # Mark veretx v as visited
    visited[v] = True
    # Assigned the pre numbering for v when we are traversing the vertex(entering the vertex)
    pre[v] = count
    # Increment the count
    count = count + 1                      
    # Repeat for each unvisited adjacent of vertex v
    for adj_vertex in AList[v]:
        if (not visited[adj_vertex]):
            # Recursively call the DFSListPrePost on unvisited adjacent of v
            count = DFSListPrePost(AList,adj_vertex,count)
    # Assigned the post numbering for v when return back from recusrive call(leaving the vertex)
    post[v] = count
    # Increment the count
    count = count + 1                           
    
    return(count)


AList = {0: [1, 4],1: [0],2: [],3: [],4: [0, 8, 9],5: [],6: [],7: [],8: [4, 9],9: [8, 4]}
DFSInitPrePost(AList)
print(DFSListPrePost(AList,0,0))
print(visited)
print(pre)
print(post)

Output

10
{0: True, 1: True, 2: False, 3: False, 4: True, 5: False, 6: False, 7: False, 8: True, 9: True}
{0: 0, 1: 1, 2: -1, 3: -1, 4: 3, 5: -1, 6: -1, 7: -1, 8: 4, 9: 5}
{0: 9, 1: 2, 2: -1, 3: -1, 4: 8, 5: -1, 6: -1, 7: -1, 8: 7, 9: 6}

 

Classifying tree edges in directed graphs using pre and post numbering

Tree edge/forward edge:

Edge (u, v) is tree/forward edge, if Interval [pre(u), post(u)] contains [pre(v), post(v)]

 

Back edge:

Edge (u, v) is back edge, if Interval [pre(v), post(v)] contains [pre(u), post(u)]

Back edges generate cycles

 

Cross edge:

Edge (u, v) is cross edge, if Intervals [pre(u), post(u)] and [pre(v), post(v)] are disjoint

 

---

 

Directed Acyclic Graph(DAG)

A Directed Acyclic Graph(DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop.

Directed acyclic graphs are a natural way to represent dependencies

• Arise in many contexts

  • Pre-requisites between courses for completing a degree
  • Recipe for cooking
  • Construction project

• Problems to be solved on DAG

  • Topological sorting
  • Longest paths

 

Topological Sort

The Topological Sort algorithm is used to sort the nodes of a directed acyclic graph (DAG) in such a way that for every directed edge from node u to node v, node u comes before node v in the sorting order.

Algorithm

Here are the steps for the Topological Sort algorithm:

1. Compute the in-degree of each node in the graph.
2. Enqueue all nodes with in-degree 0 to a queue.
3. While the queue is not empty, dequeue a node from the front of the queue and add it to the sorted list.
4. For each of the dequeued node's neighbors, decrement their in-degree by 1.
5. If any of the dequeued node's neighbors now have in-degree 0, enqueue them to the queue.
6. Repeat steps 3-5 until the queue is empty.

If the graph contains a cycle, the Topological Sort algorithm cannot produce a valid sorting order because it is impossible to order the nodes such that all edges point forward. In this case, the algorithm will terminate with an error or produce an incomplete sorting order.

To keep track of the sorting order, you can add each dequeued node to a list as it is dequeued from the queue.

 

Complexity is $O(V^2 )$ using adjacency matrix, $O(V + E)$ using adjacency list, Where $V$ is number of vertices and $E$ is number of edges in Graph.

 

Working Visualization

For given graph(DAG)

 

Implementation of Topological Sort for Adjacency list

# Implementaion of Queue
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# Implementation of Topological sort for Adjacency list
def toposortlist(AList):
    # Initialization
    (indegree,toposortlist) = ({},[])
    zerodegreeq = Queue()
    for u in AList.keys():
        indegree[u] = 0
    
    # Compute indegree for each vertex
    for u in AList.keys():
        for v in AList[u]:
            indegree[v] = indegree[v] + 1
    
    # Find the vertex with indegree 0 and added into the queue
    for u in AList.keys():
        if indegree[u] == 0:
            zerodegreeq.enqueue(u)
    
    # Topological sort Computing process
    while (not zerodegreeq.isempty()):
        # Remove one vertex from queue which have zero degree vertices
        curr_vertex = zerodegreeq.dequeue()       
        # Store the removed vertex in toposortlist and reduce the indegree by one 
        toposortlist.append(curr_vertex)
        indegree[curr_vertex] = indegree[curr_vertex]-1
        
        # Repeat for each adjacent of the removed vertex
        for adj_vertex in AList[curr_vertex]:
            # Reduce the indegree of each adjacent of the removed vertex by 1
            indegree[adj_vertex] = indegree[adj_vertex] - 1
            # If after reducing the degree of adjacent, it becomes zero then insert it into the queue
            if indegree[adj_vertex] == 0:
                zerodegreeq.enqueue(adj_vertex)                
    
    return(toposortlist)

AList={0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}
print(toposortlist(AList))

Output

[0, 1, 3, 4, 2, 5, 6, 7]

 

Code Execution Flow

 

Implementation of Topological Sort for Adjacency matrix

# Implementation of Topological sort for Adjacency matrix
def toposort(AMat):
    #Initialization
    (rows,cols) = AMat.shape
    indegree = {}
    toposortlist = []
    
    #Compute indegree for each vertex
    for c in range(cols):
        indegree[c] = 0
        for r in range(rows):
            if AMat[r,c] == 1:
                indegree[c] = indegree[c] + 1
    
    # Topological sort Computing process
    for i in range(rows):
        # Select the min level vertex for removing the graph which has indegree 0
        j = min([k for k in range(cols) if indegree[k] == 0])
        # Store the removed vertex j in toposortlist and reduce the indegree by one 
        toposortlist.append(j)
        indegree[j] = indegree[j] - 1
        
        # Reduce the indegree of each adjacent of the removed vertex j by 1
        for k in range(cols):
            if AMat[j,k] == 1:
                indegree[k] = indegree[k] - 1
                
    return(toposortlist)


edges=[(0,2),(0,3),(0,4),(1,2),(1,7),(2,5),(3,5),(3,7),(4,7),(5,6),(6,7)]
size = 8
import numpy as np
AMat = np.zeros(shape=(size,size))
for (i,j) in edges:
    AMat[i,j] = 1
print(toposort(AMat))

Output

[0, 1, 2, 3, 4, 5, 6, 7]

 

---

 

Longest Path in DAG

The Longest Path in an unweighted Directed Acyclic Graph (DAG) algorithm is used to find the maximum length path in a DAG.

Algorithm

Here are the steps for the Longest Path in an Unweighted DAG algorithm:

1. Topologically sort the nodes in the graph using the Topological Sort algorithm.
2. Initialize a distance array with all nodes set to 0 except the source node, which is set to 0.
3. For each node u in the topologically sorted order, iterate through its incoming edges (v, u) and update the distance of node u as max(dist[u], dist[v] + 1).
4. The longest path length will be the maximum value in the distance array.

 

Complexity is $O(V + E)$ using adjacency list, Where $V$ is number of vertices and $E$ is number of edges in Graph.

 

Working Visualization

For given graph(DAG)

 

Implementation for Longest Path on DAG

# Implementation of Queue
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,v):
        self.queue.append(v)
    def isempty(self):
        return(self.queue == [])
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return(v)    
    def __str__(self):
        return(str(self.queue))

# Implementation Longest path on DAG for Adjacency list
def longestpathlist(AList):
    # Initialization
    (indegree,lpath) = ({},{})
    zerodegreeq = Queue()
    for u in AList.keys():
        (indegree[u],lpath[u]) = (0,0)
    
    # Compute indegree for each vertex
    for u in AList.keys():
        for v in AList[u]:
            indegree[v] = indegree[v] + 1

    # Find the vertex with indegree 0 and added into the queue
    for u in AList.keys():
        if indegree[u] == 0:
            zerodegreeq.enqueue(u)
            
    # Longest path computing process            
    while (not zerodegreeq.isempty()):
        # Remove one vertex from queue which have zero degree vertices and reduce the indegree by 1
        curr_vertex = zerodegreeq.dequeue()
        indegree[curr_vertex] = indegree[curr_vertex] - 1
        
        # Repeat for each adjacent of the removed vertex 
        for adj_vertex in AList[curr_vertex]:
            # Reduce the indegree of each adjacent of the removed vertex by 1
            indegree[adj_vertex] = indegree[adj_vertex] - 1
            # Assign the longest path value for each adjacent of the removed vertex
            lpath[adj_vertex] = max(lpath[adj_vertex],lpath[curr_vertex]+1)
            # If after reducing the degree of adjacent, it becomes zero then insert it into the queue
            if indegree[adj_vertex] == 0:
                zerodegreeq.enqueue(adj_vertex)
                
    return(lpath)


AList={0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}
print(longestpathlist(AList))

Output

{0: 0, 1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 3, 7: 4}

Code Execution Flow

 

---

 

Visualization of graph algorithms using visualgo

Open Visualization

Select the BFS/DFS/Topological sort algorithm from left menu to visualize the working.

Source - https://visualgo.net/en/dfsbfs

---