Tarjan's Algorithm

Tarjan's algorithm is a graph algorithm designed to detect strongly connected components (SCCs) in directed graphs. The purpose of the algorithm is to partition a graph into subcomponents, identifying nodes within each component that have mutual reachability. A strongly connected component is a subgraph in which there exists a directed path between any two nodes.

Basic Working Principle

Tarjan's algorithm is based on the depth-first search (DFS) approach. Each node is assigned a unique index as it is discovered, and a lowlink value is computed for each index. The lowlink value represents the smallest index reachable from the node through its subtree in the DFS tree. During discovery, the algorithm temporarily stores nodes on a stack and identifies a strongly connected component when it is fully explored by popping the relevant nodes from the stack.

Data Structures Used

Tarjan's algorithm employs the following data structures:

• Adjacency List: To represent the graph.
• Stack: To temporarily store nodes during DFS traversal.
• Index and Lowlink Arrays: To track discovery times and lowlink values of nodes.
• onStack Array: To track whether a node is currently on the stack.
• sccs List: To store the identified strongly connected components.

Time and Space Complexity

The time complexity of Tarjan's algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This complexity arises because the algorithm processes each vertex and edge exactly once. The space complexity is O(V), due to the additional data structures used.

Applications

Tarjan's algorithm is used in various fields of computer science. Notable applications include social network analysis, compiler optimization, web crawling, biological network analysis, circuit design, dependency resolution, and network reliability analysis.

Step-by-Step Execution of Tarjan's Algorithm on an Example

Used Graph

Consider the following directed graph:

The edge list of the graph is as follows:

• 0 → 1
• 1 → 2
• 2 → 0
• 2 → 5
• 5 → 6
• 6 → 0
• 3 → 4
• 4 → 7
• 7 → 3

This graph contains two strongly connected components (SCCs):

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

Step-by-Step Execution of the Algorithm

1. DFS Start: Begin at node 0.

2. Index and Lowlink Values: Each node is assigned an index in the order of discovery. The initial lowlink value of a node is set to its own index.

3. Stack Usage: Visited nodes are pushed onto the stack.

4. Back Edges: If a visited node can reach another node already on the stack, its lowlink value is updated to the minimum of its current value and the index of the reachable node.

5. Component Detection: If a node’s lowlink value equals its index, it is the root of a strongly connected component. Nodes are popped from the stack until this root is reached, forming one SCC.

Implementation of Tarjan's Algorithm in Python

Output

^【1】 

Step-by-Step Explanation

1. Node 0 is visited (index=0, lowlink=0) and pushed onto the stack.
2. Node 1 is visited (index=1, lowlink=1) and pushed onto the stack.
3. Node 2 is visited (index=2, lowlink=2) and pushed onto the stack.
4. Since node 0 is already on the stack and is a neighbor of node 2, node 2’s lowlink is updated: lowlink[2] = 0.
5. Move to node 5, a neighbor of node 2.
6. Node 5 is visited (index=3, lowlink=3) and pushed onto the stack.
7. Move to node 6, a neighbor of node 5.
8. Node 6 is visited (index=4, lowlink=4) and pushed onto the stack.
9. Since node 0 is already on the stack and is a neighbor of node 6, node 6’s lowlink is updated: lowlink[6] = 0.
10. DFS for node 6 is complete. Node 5’s lowlink is updated: lowlink[5] = 0.
11. DFS for node 5 is complete. Node 2’s lowlink is updated: lowlink[2] = 0.
12. DFS for node 2 is complete. Node 1’s lowlink is updated: lowlink[1] = 0.
13. DFS for node 1 is complete. Node 0’s lowlink is updated: lowlink[0] = 0.
14. DFS for node 0 is complete. Since lowlink[0] == index[0], nodes are popped from the stack until node 0 is reached, forming the SCC {6, 5, 2, 1, 0}.
15. Node 3 is visited (index=5, lowlink=5) and pushed onto the stack.
16. Move to node 4, a neighbor of node 3.
17. Node 4 is visited (index=6, lowlink=6) and pushed onto the stack.
18. Move to node 7, a neighbor of node 4.
19. Node 7 is visited (index=7, lowlink=7) and pushed onto the stack.
20. Since node 3 is already on the stack and is a neighbor of node 7, node 7’s lowlink is updated: lowlink[7] = 5.
21. DFS for node 7 is complete. Node 4’s lowlink is updated: lowlink[4] = 5.
22. DFS for node 4 is complete. Node 3’s lowlink is updated: lowlink[3] = 5.
23. DFS for node 3 is complete. Nodes are popped from the stack until node 3 is reached, forming the SCC {7, 4, 3}.

History

Tarjan's algorithm was developed in 1972 by American computer scientist Robert Tarjan. The algorithm was introduced in Tarjan’s paper titled "Depth-first search and linear graph algorithms." Tarjan also contributed to the development of other data structures, including splay trees and Fibonacci heaps.

Similar Algorithms and Variants

An alternative to Tarjan's algorithm for finding strongly connected components is Kosaraju's algorithm. Kosaraju’s algorithm requires two separate DFS traversals and the reversal of the graph, whereas Tarjan’s algorithm achieves the result with a single DFS traversal. Additionally, variants optimized for parallel processing have been proposed in the literature.