Prims MST-Algorithmus in O (| V |^2)

Question

Zeitkomplexität von Prims MST-Algorithmus ist O(|V|^2), wenn Sie Adjazenzmatrix-Darstellung verwenden.

Ich versuche Prim-Algorithmus mit Adjazenz-Matrix zu implementieren. Ich verwende this als Referenz.

V = {1,2...,n} 
U = {1} 
T = NULL 
while V != U: 

    /* 
     Now this implementation means that 
     I find lowest cost edge in O(n). 
     How do I do that using adjacency list? 
    */ 

    let (u, v) be the lowest cost edge 
       such that u is in U and v is in V - U; 

    T = T + {(u,v)} 
    U = U + {v} 

EDIT:

1. Ich verstehe Prim-Algorithmus sehr gut.
2. Ich weiß, wie man es effizient mit Heaps und Prioritätswarteschlangen implementieren.
3. Ich kenne auch bessere Algorithmen.
4. Ich möchte Adjazenzmatrix-Darstellung des Graphen verwenden und O (| V |^2) Implementierung erhalten.

Ich will die ineffiziente IMPLEMENTATION

Answer 1

Sie tun es, wie in Dijkstra's algorithm, durch den Knoten, die Auswahl, die zu Ihrem aktuellen Teilbaum mit der minimalen Kosten Kante verbunden ist (dh erzeugt keinen Zyklus) . Ich denke, wikipedia erklärt Prim besser als diesen Pseudocode, den Sie haben. Schau es dir an und lass es mich wissen, wenn du weitere Fragen hast.

Answer 2

die niedrigsten Kosten Randermittlungs- ( u, v ), so dass u ist in U und V in V-U ist, wird mit einerPrioritätswarteschlange erfolgt. Genauer gesagt enthält die Prioritätswarteschlange jeden Knoten von V-U zusammen mit der niedrigsten Kostenkante von v in den aktuellen Baum U. Mit anderen Worten, die Warteschlange enthält genau | V-U | Elemente.

Nach dem Hinzufügen eines neuen Knotens u zu U, müssen Sie die Prioritäts-Warteschlange zu aktualisieren, indem geprüft wird, ob die benachbarten Knoten u kann nun durch eine Kante von geringeren Kosten als bisher erreicht werden.

Die Auswahl der Prioritätswarteschlange bestimmt die zeitliche Komplexität. Sie erhalten O (| V |^2), indem Sie die Prioritätswarteschlange als einfaches Array cheapest_edges[1..|V|] implementieren. Der Grund dafür ist, dass das Finden des Minimums in dieser Warteschlange die Zeit O (| V |) benötigt, und Sie wiederholen das | V | mal.

In Pseudo-Code:

V = {2...,n} 
U = {1} 
T = NULL 
P = array, for each v set P[v] = (1,v) 

while V != U 

    (u,v) = P[v] with v such that length P[v] is minimal 

    T = T + {(u,v)} 
    U = U + {v} 

    for each w adjacent to v 
     if length (v,w) < length P[w] then 
      P[w] = (v,w) 

Answer 3

Sie die Kanten durch die Kosten sortieren und dann die Kanten in der Reihenfolge der Kosten iterieren, und wenn diese Kante zwei unterschiedliche Subgraphen dass Kante verwenden verbindet.

Ich habe eine Implementierung here. Er liest die Anzahl der Punkte (N), die Anzahl der Kanten (M) und die Kanten in der Reihenfolge (A, B, Cost) und gibt dann die Kanten aus. Dies ist der Kruskal-Algorithmus.

Eine Implementierung des Prim-Algorithmus mit einem Heap, der die gleiche Eingabe verwendet, kann here gefunden werden.