0

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?

user3182899
  • 5

1 Answers1

0

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.

saulspatz
  • 53,131