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 Tarjan gibt es zwei "Markierungsregeln":
# Die sogenannte "Grüne Regel": -Erzeuge einen Schnitt, der keine gewählte, also grüne, Kante kreuzt. Wähle dann die kürzeste unter den unentschiedenen Kanten, die den Schnitt kreuzen und markiere diese grün.
#Die sogenannte "Rote Regel": Wähle einen einfachen Zyklus, der keine verworfene (also rote) und mindestens eine ungefärbte Kante enthält. Verwirf die längste unter den unentschiedenen Kanten im Zyklus (also markiere diese rot).
Solange einer dieser beiden Regeln anwendbar ist, soll er fortgeführt werden.
Dieser Algorithmus ist nichtdeterministisch.
Siehe auch
Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten
Algorithmus von Hopcroft und Tarjan
