Tarjan's algorithm for determining strongly connected components

The Tarjan algorithm (after its inventor Robert Tarjan ) is used in graph theory to determine the strongly connected components (SZKn) of a directed graph .

idea

The basic idea of the algorithm is to perform a depth-first search in the graph starting from a starting node . The strongly connected components (SZKn) form subtrees of the depth-search tree, the roots of these trees are called roots of the connected components .

The nodes are placed on a stack in the order in which they are visited . If the depth-first search returns from a subtree, the nodes are taken from the stack again and output, each time a decision is made as to whether the node is the root of a connected component. If so, the algorithm indicates that the nodes that have been issued so far form an SZK.

The root property

When returning from a subtree, it must be determined for each node whether it is the root of a connected component. For this purpose, a value v.lowlink is assigned to each node v in addition to the depth search index v.dfs , which numbers the nodes in the order in which they are "discovered" during the depth search , where v.lowlink : = min { v'.dfs : v 'can be reached from v over any number of edges of the graph, followed by at most one further edge (v ", v'), where v" and v 'lie in the same SCC} It applies: v is the root of a connected component if and only then if v.lowlink = v.dfs . v.lowlink can be calculated during depth first search so that the value is known at the time of the query.

Visualization

The algorithm in pseudocode

Eingabe: Graph G = (V, E)

maxdfs := 0                      // Zähler für dfs
U := V                           // Menge der unbesuchten Knoten
S := {}                          // Stack zu Beginn leer
while (es gibt ein v0 in U) do   // Solange es bis jetzt nicht erreichte Knoten gibt
  tarjan(v0)                     // Aufruf arbeitet alle von v0 erreichbaren Knoten ab
end while

procedure tarjan(v)
v.dfs := maxdfs;           // Tiefensuchindex setzen
v.lowlink := maxdfs;       // v.lowlink <= v.dfs
maxdfs := maxdfs + 1;      // Zähler erhöhen
S.push(v);                 // v auf Stack setzen
U := U \ {v};              // v aus U entfernen
forall (v, v') in E do     // benachbarte Knoten betrachten
  if (v' in U)
    tarjan(v');            // rekursiver Aufruf
    v.lowlink := min(v.lowlink, v'.lowlink);
  // Abfragen, ob v' im Stack ist. 
  // Bei geschickter Realisierung in O(1).
  // (z. B. Setzen eines Bits beim Knoten beim "push" und "pop") 
  elseif (v' in S)
    v.lowlink := min(v.lowlink, v'.dfs);
  end if
end for
if (v.lowlink = v.dfs)     // Wurzel einer SZK
  print "SZK:";
  repeat
    v' := S.pop;
    print v';
  until (v' = v);
end if

Remarks

Effort : The tarjan procedure is called exactly once for each node; the forall loop therefore considers each edge at most twice. Furthermore, an edge does not have to belong to every node. The running time of the algorithm is therefore linear in the number of edges plus the number of nodes of G.

literature

Robert Tarjan: Depth-first search and linear graph algorithms . In: SIAM Journal on Computing . Vol. 1 (1972), No. 2, pp. 146-160.