Der Kern Ihrer Frage scheint zu sein, was einen MST macht die Suche in einem gerichteten Graphen (technisch ein optimale Verzweigung oder minimal Kosten arborescence genannt) anders und deshalb schwieriger als eine MST in einem ungerichteten Graphen zu finden.
Prims und Kruskals Algorithmen funktionieren wegen der Schnitteigenschaft. 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:
2
A ----> B
| |^
1 | -99 | | 1
| v |
+-----> C
Hier ist die Minimalkosten arborescence bei A verwurzelt ist dieses:
2
A ----> B
|
-99 |
v
C
jedoch Blick auf den Schnitt ({A}, {B, C}) Der Die am wenigsten kostenintensive Kante, die diesen Schnitt kreuzt, ist die Kante (A, C), aber diese Kante taucht in keiner Minimal-Cost-Arboreszenz auf, die mit A verwurzelt ist. Ohne die Cut-Eigenschaft schlagen der Prim-Algorithmus und der Kruskal-Algorithmus beide fehl. 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 handelt es sich hier nicht um eine Arboreszenz, da sie keinen Wurzelknoten hat.
Der Standardalgorithmus zum Auffinden von Minimum-Cost-Arboreszenzen (Edmonds-Chu) ist wahrscheinlich eher im Geiste zu Boruvka's algorithm. 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!
ich Ihre Frage bearbeitet habe, die Frage nach der Suche nach einer guten Bibliothek zu entfernen, da ‚diese Art von Fragen aren t on-topic bei Stack Overflow. Aber der Rest Ihrer Frage ist wirklich interessant, also werde ich versuchen, sie zu beantworten. – templatetypedef