Tarjan's Algorithm (for SCC and Bridge Detection)

Tarjan’s Algorithm for Strongly Connected Components (SCC)

Tarjan’s algorithm is a graph traversal algorithm used to find the strongly connected components (SCCs) of a directed graph. An SCC is a subgraph where for any two vertices u and v within the subgraph, there is a path from u to v and a path from v to u.

Key Concepts

• Discovery Time (disc[u]): The time (or order) at which a node u is first visited during DFS.
• Low-link Value (low[u]): The lowest disc value reachable from u (including u itself) through the DFS tree edges and at most one back-edge.
• Stack: Used to keep track of the nodes currently in the DFS traversal path. Nodes are pushed onto the stack when visited and popped when an SCC is found.

Algorithm Steps

1. Initialize disc and low arrays with -1, and a boolean array onStack to false.
2. Maintain a global time variable, initialized to 0.
3. For each unvisited vertex u in the graph, call dfs(u): a. Set disc[u] = low[u] = time++. b. Push u onto the stack and set onStack[u] = true. c. For each neighbor v of u: i. If v is not visited (disc[v] == -1): 1. Recursively call dfs(v). 2. Update low[u] = min(low[u], low[v]). ii. If v is visited and onStack[v] is true: 1. Update low[u] = min(low[u], disc[v]) (this is a back-edge). d. If low[u] == disc[u] (meaning u is the root of an SCC): i. Pop nodes from the stack until u is popped, forming an SCC. ii. Set onStack to false for popped nodes.

Time and Space Complexity

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited once.
• Space Complexity: O(V + E) for adjacency list, disc, low, onStack arrays, and the stack.

Tarjan’s Algorithm for Bridge Detection

Tarjan’s algorithm can also be adapted to find bridges in an undirected graph. A bridge is an edge whose removal increases the number of connected components of the graph.

Key Concepts (similar to SCC, but for undirected graphs)

• Discovery Time (disc[u]): The time at which a node u is first visited during DFS.
• Low-link Value (low[u]): The lowest disc value reachable from u (including u itself) through the DFS tree edges and at most one back-edge (excluding the edge to its immediate parent in the DFS tree).

Algorithm Steps

1. Initialize disc and low arrays with -1, and a parent array with -1.
2. Maintain a global time variable, initialized to 0.
3. For each unvisited vertex u in the graph, call dfs(u, -1) (initial parent is -1): a. Set disc[u] = low[u] = time++. b. For each neighbor v of u: i. If v is the parent of u, continue. ii. If v is not visited (disc[v] == -1): 1. Set parent[v] = u. 2. Recursively call dfs(v, u). 3. Update low[u] = min(low[u], low[v]). 4. If low[v] > disc[u], then the edge (u, v) is a bridge. iii. If v is visited and not the parent of u: 1. Update low[u] = min(low[u], disc[v]) (this is a back-edge).

Time and Space Complexity

• Time Complexity: O(V + E).
• Space Complexity: O(V + E).