Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten

Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines Graphen.

Inhaltsverzeichnis

Idee

Die Grundidee des Algorithmus besteht darin, von einem Startknoten ausgehend eine Tiefensuche im Graphen durchzuführen. Die SZKn bilden dabei Teilbäume des Tiefensuchbaumes, die Wurzeln dieser Bäume heißen Wurzeln der Zusammenhangskomponenten.

Die Knoten werden in der Reihenfolge, in der sie besucht werden, auf einem Stack abgelegt. Kehrt die Tiefensuche aus einem Unterbaum zurück, werden die Knoten wieder vom Stack genommen und ausgegeben, dabei wird jedes Mal entschieden, ob es sich bei dem Knoten um die Wurzel einer Zusammenhangskomponente handelt. Wenn ja, zeigt der Algorithmus an, dass die bisher ausgegebenen Knoten eine SZK bilden.

Die Wurzeleigenschaft

Für den Algorithmus ist offenbar entscheidend, dass beim Zurückkehren aus einem Unterbaum für jeden Knoten festgestellt werden kann, ob er die Wurzel einer Zusammenhangskomponente ist. Dazu wird jedem Knoten v neben dem Tiefensuchindex v.dfs, welcher die Knoten in der Reihenfolge durchnummeriert, in der sie bei der Tiefensuche "entdeckt" werden, ein Wert v.lowlink zugeordnet, wobei

v.lowlink := min {v'.dfs: v' ist von v erreichbar über beliebig viele Baumkanten, gefolgt von maximal einer weiteren Kante (v", v'), wobei v" und v' in derselben SZK liegen}

Es gilt nun: v ist die Wurzel einer Zusammenhangskomponente genau dann, wenn v.lowlink = v.dfs ist. v.lowlink kann während der Tiefensuche so berechnet werden, dass der Wert zum Zeitpunkt der Abfrage bekannt ist.

Der Algorithmus 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 unerreichbare 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

Bemerkungen

  1. Aufwand: Die Prozedur tarjan wird für jeden Knoten genau einmal aufgerufen; die forall-Schleife betrachtet also jede Kante insgesamt höchstens zweimal. Des Weiteren muss aber nicht zu jedem Knoten eine Kante gehören. Die Laufzeit des Algorithmus ist also linear in der Anzahl der Kanten plus der Anzahl der Knoten von G.

Siehe auch

Literatur

  • Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Bd. 1 (1972), Nr. 2, S. 146-160.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes — Der Algorithmus von Tarjan wird in der Graphentheorie benutzt, um minimale Spannbäume zu bestimmen. Für die Kantenauswahl nach Robert Tarjan gibt es zwei Markierungsregeln: Die sogenannte Grüne Regel: Erzeuge einen Schnitt, der keine gewählte,… …   Deutsch Wikipedia

  • Algorithmus von Tarjan — In der Graphentheorie werden unterschiedliche Algorithmen nach Robert Tarjan benannt: Der Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten Der Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes Der Algorithmus …   Deutsch Wikipedia

  • Robert Endre Tarjan — (* 30. April 1948 in Pomona, Kalifornien) ist ein US amerikanischer Informatiker. 1986 wurde er zusammen mit John E. Hopcroft für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award ausgezeichnet. Er ist Professor… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Robert Tarjan — 2010 Robert „Bob“ Endre Tarjan (* 30. April 1948 in Pomona, Kalifornien) ist ein amerikanischer Informatiker. 1986 wurde er zusammen mit John E. Hopcroft für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award… …   Deutsch Wikipedia

  • Artikulation (Graphentheorie) — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia

  • Block (Graphentheorie) — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia

  • Blockgraph — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia

  • Blockgraph (Graphentheorie) — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia

  • Brücke (Graphentheorie) — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”