Strongly Connected Components

...

1. Initialize the algorithm by setting the index and low-link value of each node to -1. Create an empty stack.
2. Perform a DFS traversal of the graph, starting from each unvisited node.
3. Assign a unique index to each visited node and set its low-link value to the index initially.
4. Push the visited node onto the stack.
5. For each neighbor of the current node:
   • If the neighbor has not been visited, recursively perform a DFS on it.
   • Update the low-link value of the current node using the minimum of its own low-link value and the low-link value of the neighbor.
6. If the current node's low-link value is equal to its index, the current node and all nodes above it in the stack belong to the same SCC. Pop these nodes from the stack and mark them as part of the SCC.
7. Continue the DFS traversal until all nodes have been visited.

function TarjanSCC(graph):
    index := 0
    stack := empty stack
    indexMap := map of nodes to their index values
    lowLinkMap := map of nodes to their low-link values
    onStack := set of nodes on the stack
    SCCs := empty list

    for each node in graph:
        if node is unvisited:
            DFS(node)

    function DFS(node):
        indexMap[node] := index
        lowLinkMap[node] := index
        index := index + 1
        stack.push(node)
        onStack.add(node)

        for each neighbor in neighbors of node:
            if neighbor is unvisited:
                DFS(neighbor)
                lowLinkMap[node] := minimum(lowLinkMap[node], lowLinkMap[neighbor])
            else if neighbor is on stack:
                lowLinkMap[node] := minimum(lowLinkMap[node], indexMap[neighbor])

        if lowLinkMap[node] == indexMap[node]:
            SCC := empty list
            while true:
                poppedNode := stack.pop()
                onStack.remove(poppedNode)
                SCC.add(poppedNode)
                if poppedNode == node:
                    break
            SCCs.add(SCC)

    return SCCs
Copy

Tarjan's algorithm uses DFS to visit nodes in the graph and assigns each node an index and low-link value. The index represents the order in which the nodes are visited during the DFS traversal, and the low-link value is the minimum index of any node reachable from the current node.

The algorithm maintains a stack to keep track of the visited nodes. When a node is visited, it is pushed onto the stack and marked as on the stack. The algorithm performs a recursive DFS on each unvisited neighbor of the current node, updating the low-link value of the current node based on the low-link values of its neighbors.

If the low-link value of a node is equal to its index, it means that the current node and all nodes above it in the stack form a strongly connected component. These nodes are popped from the stack and added to a list representing the SCC.

The algorithm continues the DFS traversal until all nodes have been visited. At the end, the algorithm returns a list of SCCs present in the graph.

Tarjan's algorithm is efficient for finding SCCs in a graph and has a time complexity of , where V is the number of vertices and is the number of edges in the graph. This time complexity arises from the fact that each node and each edge is visited once during the DFS traversal.