Does Tarjan’s algorithm actually find all SCCs

directed graphs

So I learned about Tarjan's algorithm the other day and I'm not quite sure if I understand it 100% correctly. I read a lot about the statement that Tarjan's algorithm is able to decompose a directed graph (digraph) into its strongly connected components (SCCs). An SCC being defined as a partition of the digraph with the condition that all of the component's nodes can be reached from every other node in that component.

Suppose I have the following digraph:

Example Digraph

To my understanding, the graph has two SCCs: one formed by the three nodes to the left, the second by the three nodes to the right. If I understand Tarjan's algorithm correctly however, it will only detect the "left" SCC, because the "right" one does not contain a cycle, is that correct? In this case, the statement that Tarjan's algorithm finds SCCs is not entirely correct?

Best Answer

I did a quick and dirty python implementation of the algorithm as described in the Wikipedia article, and tested it on your digraph.

# Implement Trajan's algorithm for strongly connected components

SCC = []
indices = { }
lowlinks = { }
stack = []
index = 0

G = {1:[3], 2:[1,4],3:[2],4:[5],5:[4,6],6:[5]}

def strongConnect(v):
    global index
    
    indices[v] = index
    lowlinks[v] = index
    index += 1
    stack.append(v)
    for w in G[v]:
        if w not in indices:
            strongConnect(w)
            lowlinks[v] = min(lowlinks[v], lowlinks[w])
        elif w in stack:
            lowlinks[v] = min(lowlinks[v], indices[w])
    if lowlinks[v] == indices[v]:
        scc = []
        while True:
            w = stack.pop(-1)
            scc.append(w)
            if w == v:
                break
        SCC.append(scc)
            
for v in G:
    if v not in indices:
        strongConnect(v)
        
for scc in SCC:
    print(scc)

This outputs

[6, 5, 4]
[2, 3, 1]

so the algorithm does indeed work in this case. The algorithm is very well known, and the chance that it is incorrect is negligible.

Related Question