Tarjan’s Algorithm in Python
Tarjan’s algorithm is used to find strongly connected components (SCCs) in a directed graph. It efficiently finds groups of vertices such that each vertex in a group has a path to every other vertex in the same group.
Let’s illustrate the working of Tarjan’s algorithm with an example:
Consider the following directed graph:
0 --> 1 --> 2 <--+
^ |
| v
+--- 6 <-- 5 ---+
| ^
v |
3 --> 4 --> 7 --+
How to implement Tarjan’s Algorithm in Python?
- Initialization:
- Initialize TarjanSCC object with the graph.
- Initialize variables to track low link values, visited vertices, and SCCs.
- DFS Traversal:
- Start DFS traversal from each unvisited vertex.
- Assign low link values to vertices.
- Maintain a stack of vertices on the current DFS path.
- Identify SCCs based on low link values.
- Output SCCs:
- Output the strongly connected components found by the algorithm.
Tarjan’s Algorithm in Python:
class TarjanSCC:
def __init__(self, graph):
self.graph = graph
self.time = 0
self.stack = []
self.low_link = {}
self.visited = set()
self.sccs = []
def _dfs(self, v):
self.low_link[v] = self.time
self.time += 1
self.stack.append(v)
self.visited.add(v)
for neighbor in self.graph[v]:
if neighbor not in self.low_link:
self._dfs(neighbor)
self.low_link[v] = min(self.low_link[v], self.low_link[neighbor])
elif neighbor in self.stack:
self.low_link[v] = min(self.low_link[v], self.low_link[neighbor])
if self.low_link[v] == v:
scc = []
while True:
u = self.stack.pop()
scc.append(u)
if u == v:
break
self.sccs.append(scc)
def find_sccs(self):
for v in self.graph:
if v not in self.low_link:
self._dfs(v)
return self.sccs
# Example usage:
graph = {
0: [1],
1: [2],
2: [0, 3],
3: [4],
4: [5, 7],
5: [6],
6: [0, 2, 5],
7: [3, 5, 8],
8: [4, 7]
}
tarjan = TarjanSCC(graph)
sccs = tarjan.find_sccs()
print("Strongly Connected Components:")
for scc in sccs:
print(scc)
Output
Strongly Connected Components: [8, 7, 6, 5, 4, 3, 2, 1, 0]
Complexity Analysis:
- Time Complexity: Tarjan’s algorithm has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
- Space Complexity: The space complexity of the algorithm is O(V), where V is the number of vertices, due to the stack used in DFS traversal