Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes

Der Algorithmus von Tarjan ist eine Färbemethode in der Graphentheorie, um einen minimalen Spannbaum (MST) 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.

Er ist nicht mit dem randomisierten Algorithmus zur Lösung des MST-Problems von Tarjan, David R. Karger und Philip N. Klein von 1995 zu verwechseln.

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.