Ist der ungerichtete Graph MST-Algorithmus (Prim oder Kruskal) eine allgemeine Form des gerichteten MST-Algorithmus (Edmond / Chiu)? Warum ist es so schwierig, den MST-Quellcode für den gerichteten Fall zu finden? Können wir die ungerichtete Lösung verwenden, um die MST in einem gerichteten Graphen zu erhalten?
Dies bezieht sich auf Folgendes: Warum können nicht die Algorithmen von Prim oder Kruskal verwendet werden? auf einem gerichteten Graphen verwendet werden?
Der Kern Ihrer Frage scheint zu sein, was das Auffinden einer MST (technisch als optimale Verzweigung oder minimum-cost arborescence bezeichnet) in einem gerichteten Graphen anders und daher schwieriger macht als eine MST in einem ungerichteten Graphen zu finden.
Die Algorithmen von Prim und Kruskal funktionieren wegen der cut -Eigenschaft . Wenn G = (V, E) ein Graph ist, dann muss für jeden Schnitt (S, V - S) in G, wenn es eine billigste Kante {u, v} gibt, die diesen Schnitt kreuzt, diese Kante zu allen MSTs gehören von G. Leider ist diese Eigenschaft im gerichteten Fall nicht wahr. Hier ist ein Gegenbeispiel:
%Vor%Hier ist die bei A verwurzelte Struktur mit minimalen Kosten die folgende:
%Vor%Sehen Sie sich jedoch den Schnitt ({A}, {B, C}) an. Die Kante mit den geringsten Kosten, die diesen Schnitt schneidet, ist die Kante (A, C), aber diese Kante erscheint nicht in einer Baumstruktur mit minimalen Kosten in A verwurzelt.
Ohne die cut -Eigenschaft scheitern sowohl der Prim-Algorithmus als auch der Kruskal-Algorithmus. Versuchen Sie, Prims Algorithmus in dem hier angegebenen Diagramm auszuführen, beginnend mit Knoten A als Ihrem eingeschlossenen Knoten. Sie fügen die Kante (A, C) und dann die Kante (C, B) hinzu, was zu einer suboptimalen Verzweigung führt. Versuchen Sie nun, Kruskals Algorithmus hier auszuführen. Sie fügen zuerst die Kante (B, C) hinzu und fügen dann die Kante (A, C) hinzu. Leider ist dies keine Arboreszenz, weil es keinen Wurzelknoten hat.
Der Standardalgorithmus zum Auffinden von Arborcenzen mit minimalen Kosten (Edmonds-Chu) ist tatsächlich wahrscheinlich näher an Boruvkas Algorithmus . Boruvkas Algorithmus arbeitet, indem er für jeden Knoten gleichzeitig die kostengünstigste Kante auswählt, die mit diesem Knoten verbunden ist, und sie zu der Kandidaten-MST hinzufügt. Dann kontrahieren Sie alle auf diese Weise gebildeten CCs in einzelne Knoten und wiederholen diesen Vorgang, bis Sie Ihren Baum haben.
Im gerichteten Fall, solange die Kantengewichte verschieden sind, wird dieser Algorithmus niemals einen Zyklus einführen (es ist eine gute Übung, dies zu beweisen), aber dies ist bei gerichteten Algorithmen nicht der Fall. Die obige Grafik ist ein gutes Beispiel dafür - wenn Sie dies versuchen, wählen Sie (A, C) von A, (C, B) von C und (B, C) von B, um den Zyklus (B, C , B). Die Korrektur, die der Edmonds-Chu-Algorithmus verwendet, arbeitet, indem einer dieser Zyklen zu einem einzigen Knoten kontrahiert wird, dieser Prozess dann in dem reduzierten Graphen wiederholt wird und die Zyklen basierend auf dem Ergebnis "unkontrahiert" werden. In diesem Sinne ist es dem Boruvka-Algorithmus ähnlich, allerdings mit entsprechenden Modifikationen.
Hoffe, das hilft!
Tags und Links algorithm graph-algorithm graph tree