Implementation of Kosaraju’s Algorithm in Python
Here’s a Python implementation of Kosaraju’s Algorithm:
from collections import defaultdict, deque
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def _dfs(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self._dfs(neighbor, visited, stack)
stack.append(v)
def _transpose(self):
transposed_graph = Graph(self.V)
for node in self.graph:
for neighbor in self.graph[node]:
transposed_graph.add_edge(neighbor, node)
return transposed_graph
def _fill_order(self, visited, stack):
for i in range(self.V):
if not visited[i]:
self._dfs(i, visited, stack)
def _dfs_util(self, v, visited, component):
visited[v] = True
component.append(v)
for neighbor in self.graph[v]:
if not visited[neighbor]:
self._dfs_util(neighbor, visited, component)
def kosaraju_scc(self):
stack = deque()
visited = [False] * self.V
self._fill_order(visited, stack)
transposed_graph = self._transpose()
visited = [False] * self.V
scc_list = []
while stack:
node = stack.pop()
if not visited[node]:
component = []
transposed_graph._dfs_util(node, visited, component)
scc_list.append(component)
return scc_list
# Example usage
if __name__ == "__main__":
g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)
sccs = g.kosaraju_scc()
print("Strongly Connected Components:", sccs)
Output
Strongly Connected Components: [[0, 1, 2], [3], [4]]
Time complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary space: O(V+E)