Tarjan's algorithm is a renowned method used in graph theory to find strongly-connected components (SCCs) in a directed graph. This is an essential problem, particularly in the realm of computer science, with applications ranging from compiler design to network analysis. The algorithm is both efficient and elegant, utilizing depth-first search (DFS) to linear time complexity with respect to the number of vertices and edges.

One of the key features of Tarjan's algorithm is the use of indices and low-link values, underpinning why indexing in the back edge is crucial.

Understanding Strongly-Connected Components

A strongly-connected component of a directed graph is a maximal subgraph in which every vertex is reachable from every other vertex. In simpler terms, for any two vertices `u` and `v` within an SCC, there is always a path from `u` to `v` and vice versa.

Marvels of Tarjan's Algorithm

The genius of Tarjan's SCC algorithm lies in its clever use of depth-first search. The algorithm performs the following steps:

1. Start DFS: Begin DFS traversal of the graph, assigning each vertex a unique index along the way. This index helps track the order in which vertices are visited.
2. Low-link Values: Alongside the index, each vertex is assigned a low-link value, which serves as a crucial element for identifying SCCs. The low-link value of a vertex `v` is the smallest index reachable from `v` through its DFS subtree, which is essentially the smallest index of vertices that `v` can reach considering potential back edges.
3. Backtracking: During the DFS traversal, the algorithm backtracks when it finishes processing a node. At this point, it checks the relation between the node's index and its low-link value to determine whether the node is a root node of an SCC. If a vertex's index equals its low-link value, it signifies the start of an SCC.
4. Forming SCCs: As nodes are explored, they are pushed onto a stack. Once an SCC is identified (i.e., during backtracking when a root node is detected), nodes from the top of the stack are popped until the root node is reached, forming the strongly-connected component.

Why Index in the Back Edge?

Back edges represent connections pointing from a node to one of its ancestors in the DFS tree, and managing these edges effectively is crucial for the correctness of the algorithm. The index in the back edge is vital to ensure that the relationship between nodes in terms of connectivity and reachability is accurately captured. Indices allow the algorithm to:

1. Track Visitation Order: By keeping track of the order of visitation, indices help identify cycles and relationships among nodes accurately.
2. Determine Low-link Values: With the use of indices, calculating the correct low-link values becomes feasible, as it's essential to identify the earliest reachable ancestor (from a given subtree).
3. Detect Root Nodes for SCCs: Index comparison is essential for determining root nodes through the condition `index(v) == low-link(v)`. It helps recognize when an SCC begins and ends during backtracking.
4. Efficiently Identify Cycles: By checking indices with back edges, cycles can be detected and managed within the graph ensuring proper SCC formation.

Example

Consider a simple directed graph:

• Node A: Start DFS, `index(A) = 1`, `low-link(A) = 1`.
• Node B: Move to B, `index(B) = 2`, `low-link(B) = 2`.
• Node C: Move to C, `index(C) = 3`, `low-link(C) = 3`.
• Node D: Move to D, `index(D) = 4`, `low-link(D) = 4`.
• Back Edge from D to C: Update `low-link(D) = min(low-link(D), index(C)) = 3`.
• Node D to F: Proceed to F, `index(F) = 5`, `low-link(F) = 5`.
• Finish F: No outward edges from F. Backtrack, update, and check low-link value.
• Backtracking D, C: Continue with low-link comparisons.