Warum können die Algorithmen von Prim oder Kruskal nicht in einem gerichteten Graphen verwendet werden?

Question

Die Algorithmen von Prim und Kruskal werden verwendet, um den minimalen Spannbaum eines Graphen zu finden, der verbunden und ungerichtet ist. Warum können sie nicht auf einem gerichteten Diagramm verwendet werden?

Answer 1

Es ist ein kleines Wunder, dass diese Algorithmen in erster Linie funktionieren - die meisten gierigen Algorithmen stürzen ab und zu ab. Angenommen, Sie möchten diese verwenden, um einen minimalen Spannbaum zu finden (gerichtete Pfade von einem Knoten zu allen anderen), dann sieht ein problematischer Graph für Kruskal so aus.

5 
    --> a 
//^ 
s 1| |2 
\ v/
    --> b 
3 

Wir werden die a- nehmen> b Bogen der Kosten 1, dann stecken, weil wir wirklich s-> b der Kosten 3 und b-> Prim wollte eine Kosten 2.

Für , diese Grafik ist problematisch.

5 
    --> a 
//
s 1| 
\ v 
    --> b 
3 

Wir nehmen s-> b von Kosten 3, aber wir wirklich s- gesucht> eine Kosten 5 und a-> b Kosten 1.

Answer 2

Prim und Kruskals Algorithmus Ausgang ein Minimum Spanning Tree für verbundene und "ungerichtete" Graphen. Wenn es nicht verbunden ist, können wir sie optimieren, um minimal überspannende Gesamtstrukturen auszugeben.

In Prim-Algorithmus teilen wir das Diagramm in zwei Gruppen von Vertices. Ein Satz der erkundeten Scheitelpunkte, die bereits MST (Set1) und einen weiteren Satz von unerforschten Scheitelpunkten gebildet haben, die sich schließlich dem ersten Satz anschließen, um "spanning" (Satz2) zu vervollständigen. Zu jedem Zeitpunkt wählen wir eine minimale gewichtete Kante in dem Schnitt, der die zwei disjunkten Sätze verbindet. Wenn es von den erkundeten Knoten der MST keine gerichtete Kante gibt, um unerforscht zu bleiben, bleibt der Algorithmus stecken, obwohl Kanten von unerforschten Knoten zu erkundeten Knoten in MST vorhanden sind. Im Kruskal-Algorithmus besteht die Idee darin, die Kanten in aufsteigender Reihenfolge nach ihrem Gewicht zu sortieren und sie in der Reihenfolge aufzufangen und sie in MST-erkundete Knoten/Kanten aufzunehmen, wenn sie nicht bereits einen Zyklus mit erkundeten Knoten bilden. Dies wird von Union-Find DS getan. Die Erkennung eines Zyklus für gerichtete Graphen schlägt jedoch mit dieser Methode fehl. Für Beispiel: Graph mit Kanten [1-> 2] [2-> 3] [1-> 3] enthält einen Zyklus mit der Union-Find-Methode.

So Prims schlägt fehl, da es annimmt, dass jeder Knoten von jedem Knoten aus erreichbar ist, der für ungerichtete Graphen für Digraphen möglicherweise nicht zutreffend ist. Kruskal schlägt fehl, weil Zyklen nicht erkannt werden, und manchmal ist es wichtig, Kanten hinzuzufügen, die Zyklen bilden, um die "minimale" gewichtete Eigenschaft von MST zu erfüllen.

Auch bei Digraphen macht MST keinen Sinn. Sein Äquivalent für Digraphen ist "minimum spanning arborescence", das einen Baum erzeugt, in dem jeder Eckpunkt von einem einzigen Eckpunkt aus erreicht werden kann.