Kosaraju’s Algorithm

In the world of Computer Science, Graphs are non-arguably considered to be the most important forms of data structures. Everything that makes our lives easier, Fingerprint Recognition, Communication Networks like roads and flights, Social Networks, Google Maps, even the entire Internet itself, are based on the core concepts of Graph Theory.

Theoretically, a Graph is a non-linear data structure, that can be defined as a pictorial representation of objects or nodes called ‘Vertices’, which are interconnected using lines or paths called ‘Edges’. The following is an example of an Undirected Graph. In an Undirected Graph, the edges are bidirectional, with no direction associated with them. Hence, the graph can be traversed in either direction. The absence of an arrow tells us that the graph is undirected.

Undirected Graph

A Directed Graph is a graph where each edge has a direction associated with it. Edges are usually represented by arrows pointing in the direction the graph can be traversed. The following is an example of a Directed Graph.

Directed Graph

The following code snippet shows the basic definition of a Graph ADT (in the form of an adjacency list) in Python.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for i in range(vertices)]
    def addEdge(self, u, v):
        self.graph[u].append(v)

A Directed Graph in which every vertex is reachable from every other vertex is called a Strongly Connected Graph. Every Strongly Connected subgraph of a given arbitrary Directed Graph is called a Strongly Connected Component of the given Directed Graph.

Strongly Connected Components of a Directed Graph

Kosaraju’s Algorithm is designed to detect all the Strongly Connected Components of a given Directed Graph in linear Time Complexity. A prerequisite of understanding Kosaraju’s Algorithm is understanding the Depth First Search Algorithm used for graph traversal.

Depth First Search Approach

First, we select an arbitrary node of the graph as a root node and mark the node as visited. Then we move to its adjacent unvisited node and continue the loop until we reach the end of the branch, visiting all the nodes present in the branch. Then we backtrack and check for other unvisited nodes and recursively traverse all the possible branches in a similar fashion. Thereby, we can find all the nodes that are reachable from the chosen root node.

Depth First Search Algorithm

1. Choose an arbitrary node as the root node, and mark it as visited.
2. Traverse all the adjacent unmarked nodes and call the function recursively for the unmarked adjacent nodes as the root nodes.

The following is a code snippet for the Depth First Search Algorithm in Python.

def DFSUtility(self, v, visited):
    visited[v] = True
    print(v, end=" ")
    for i in self.graph[v]:
        if not visited[i]:
        self.DFSUtility(i, visited)

Depth First Search Time Complexity

While traversing a Directed Graph which is represented using an adjacency list, we process each vertex and all the edges connecting it to its neighboring nodes. This gives us a net Time Complexity of O(V) + O(E) = O(V + E), where V is the total number of vertices and E is the total number of edges.

Kosaraju’s Algorithm

Kosarju’s Algorithm is a DFS based algorithm, in which we perform the Depth First Search twice.

• First, we apply a modified version of DFS on the given Directed Graph, in which, instead of printing the nodes after visiting them, we first call the recursive function for the adjacent unvisited nodes of the vertex and then push this vertex into a stack. What this step basically does, is that it traverses all the possible paths that a vertex leads to, and after backtracking, it pushes this vertex into a stack. The following snippet shows the implementation of this function in Python.

def fillStack(self, v, visited, stack):
    visited[v] = True
    for i in self.graph[v]:
        if not visited[i]:
        self.fillStack(i, visited, stack)
    stack.append(v)

• Next, we transpose the graph. Transposing a Directed Graph basically means, to reverse the directions of all the edges present in the graph. The implementation of this function in Python is as follows.

def getTranspose(self):
    g = Graph(self.V)
    for i in range(self.V):
        for j in self.graph[i]:
            g.addEdge(j, i)
    return g

• Ultimately, we keep popping vertices from the stack generated in the first step and run a Depth First Search with each vertex as the root node, if it has not already been visited. The final code implementation of Kosaraju’s Algorithm in Python is as follows.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for i in range(vertices)]

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtility(self, v, visited):
        visited[v] = True
        print(v, end=" ")
        for i in self.graph[v]:
            if not visited[i]:
            self.DFSUtility(i, visited)

    def fillStack(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
            self.fillStack(i, visited, stack)
        stack.append(v)

    def getTranspose(self):
        g = Graph(self.V)
        for i in range(self.V):
            for j in self.graph[i]:
            g.addEdge(j, i)
        return g

    def kosarajuSCC(self):
        stack = []
        visited = [False] * self.V
        for i in range(self.V):
            if not visited[i]:
            self.fillStack(i, visited, stack)
        transpose = self.getTranspose()
        visited = [False] * self.V
        while stack:
            i = stack.pop()
            if not visited[i]:
                transpose.DFSUtility(i, visited)
                print("")

Now, let’s take an example to test the algorithm. Let the following be a given arbitrary Directed Graph.

Example

We can add the main function to our code to create the graph and call Kosaraju’s Algorithm to print the set of Strongly Connected Components of the given graph.

if __name__ == '__main__':
    g = Graph(10)
    g.addEdge(0, 1)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 8)
    g.addEdge(8, 9)
    g.addEdge(1, 3)
    g.addEdge(3, 4)
    g.addEdge(4, 5)
    g.addEdge(5, 6)
    g.addEdge(6, 3)
    g.addEdge(5, 7)

    print('The Strongly Connected Components are:')
    g.kosarajuSCC()

On running the code in the terminal, we get the following output.

PS D:\Algorithms\Kosaraju> python .\kosarajualgo.py
The Strongly Connected Components are:
0 2 1
3 6 5 4
7
8
9

Voila! We have successfully detected all the Strongly Connected Components of the given Directed Graph!

Kosaraju’s Algorithm Time Complexity

In Kosaraju’s Algorithm, we perform Depth First Search on the Directed Graph twice. This gives us a net Time Complexity of O(V + E). Hence, Kosaraju’s Algorithm helps us in detecting all the Strongly Connected Components of a given Directed Graph in Linear Time Complexity, proving itself to be one of the most efficient algorithms in Graph Theory.

Detection of Strongly Connected Components is used as the first step in many algorithms to simplify the graph when the size of the data is too large or when a grouping of data is required. It has many real-world applications, for example generating recommendations on social media platforms like Facebook, generating routes between points in different clustered areas in Google Maps, designing Communication Networks, etc. Therefore, an efficient algorithm like Kosaraju’s Algorithm has immense use in the real-world and will continue to be one of the most important and most used algorithms of all time.

Thank you so much readers for staying with me till the end of the article. I hope I was able to clearly explain all the core aspects of Kosaraju’s Algorithm and you found this article helpful. See you next time! Till then Keep Reading and Keep Coding!!