Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes
Der Algorithmus von Tarjan wird in der Graphentheorie benutzt, um einen minimalen Spannbaum in einem ungerichteten zusammenhängenden Graphen zu bestimmen.
Es handelt sich dabei um einen Greedy-Algorithmus, der in jedem Schritt genau eine Kante des Graphen entweder für den minimalen Spannbaum auswählt (grün färbt) oder verwirft (rot färbt). Das geschieht nach zwei Markierungsregeln:
- Grüne Regel
- Wähle einen Schnitt, der mindestens eine ungefärbte aber noch keine grüne Kante enthält. Färbe die kürzeste unter den ungefärbten Kanten des Schnittes grün.
- Rote Regel
- Wähle einen einfachen Kreis, der keine rote und mindestens eine ungefärbte Kante enthält. Färbe die längste unter den ungefärbten Kanten im Kreis rot.
Robert Tarjan hat gezeigt, dass bei Beachtung dieser Regeln in einem Graphen immer ein minimaler Spannbaum existiert, der alle grünen, aber keine roten Kanten enthält. Zudem ist immer (mindestens) eine der beiden Regeln anwendbar, solange noch nicht alle Kanten des Graphen rot oder grün gefärbt sind. Am Ende bilden die grünen Kanten den gesuchten minimalen Spannbaum.
Für einen ausführbaren Algorithmus muss die Reihenfolge der Verwendung der beiden Regeln konkret festgelegt werden. Dies führt beispielsweise zum Algorithmus von Kruskal oder zum Algorithmus von Prim. Beide sind Spezialfälle des Algorithmus von Tarjan. Beim Prim-Algorithmus wird systematisch nur die grüne Regel angewendet bis ein Spannbaum gefunden ist.
Siehe auch
Literatur
- Dorothea Wagner: Aufspannende Bäume minimalen Gewichts. (Kapitel 10, S. 173–183) In: Thomas Ottmann (Hrsg.): Prinzipien des Algorithmenentwurfs. Spektrum Akademischer Verlag Heidelberg, Berlin 1998. ISBN 3-8274-0238-7.