Strongly Connected Components (SCC) in Python ❤️

Strongly Connected Components (SCCs) in a directed graph are groups of vertices where each vertex has a path to every other vertex within the same group. SCCs are essential for understanding the connectivity structure of directed graphs.

Kosaraju’s Algorithm:

Kosaraju’s algorithm is a popular method for finding SCCs in a directed graph. It consists of two main steps:

DFS on the Original Graph: Perform a depth-first search (DFS) on the original graph and store the finishing times of vertices.
DFS on the Transposed Graph: Perform a DFS on the transposed graph (graph with reversed edges) using vertices sorted by their finishing times from the first step.

Step-by-step algorithm:

Graph Representation:
- Represent the directed graph using an adjacency list.
DFS on Original Graph:
- Perform DFS traversal on the original graph to create a stack based on finishing times.
Transpose the Graph:
- Obtain the transpose of the original graph by reversing the direction of all edges.
DFS on Transposed Graph:
- Perform DFS traversal on the transposed graph using vertices popped from the stack obtained in step 2.
Identify SCCs:
- Each DFS traversal on the transposed graph results in a strongly connected component.

Python Implementation:

Python

# Python program to check if a given directed graph is strongly
# connected or not

from collections import defaultdict

# This class represents a directed graph using adjacency list representation


class Graph:

    def __init__(self, vertices):
        self.V = vertices # No. of vertices
        self.graph = defaultdict(list) # default dictionary to store graph

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A function used by isSC() to perform DFS
    def DFSUtil(self, v, visited):

        # Mark the current node as visited
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    # Function that returns reverse (or transpose) of this graph

    def getTranspose(self):

        g = Graph(self.V)

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph:
            for j in self.graph[i]:
                g.addEdge(j, i)

        return g

    # The main function that returns true if graph is strongly connected
    def isSC(self):

        # Mark all the vertices as not visited (For first DFS)
        visited =[False]*(self.V)
        
        # Do DFS traversal starting from first vertex.
        self.DFSUtil(0,visited)

        # If DFS traversal doesnt visit all vertices, then return false
        if any(i == False for i in visited):
            return False

        # Create a reversed graph
        gr = self.getTranspose()
        
        # Mark all the vertices as not visited (For second DFS)
        visited =[False]*(self.V)

        # Do DFS for reversed graph starting from first vertex.
        # Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(0,visited)

        # If all vertices are not visited in second DFS, then
        # return false
        if any(i == False for i in visited):
            return False

        return True

# Create a graph given in the above diagram
g1 = Graph(5)
g1.addEdge(0, 1)
g1.addEdge(1, 2)
g1.addEdge(2, 3)
g1.addEdge(3, 0)
g1.addEdge(2, 4)
g1.addEdge(4, 2)
print ("Yes" if g1.isSC() else "No")

g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print ("Yes" if g2.isSC() else "No")

Output

Yes
No

Time Complexity: Time complexity of above implementation is same as Depth First Search which is O(V+E) if the graph is represented using adjacency list representation.
Auxiliary Space: O(V)

Strongly Connected Components (SCC) in Python

Kosaraju’s Algorithm:

Contact Us