Prim's Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 34: Line 34:
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/bYMq1/fast-implementation-i}}
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/bYMq1/fast-implementation-i}}
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/qzdR8/fast-implementation-ii}}
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/qzdR8/fast-implementation-ii}}
<font color=darkkhaki>Add summary here.</font>

Revision as of 23:42, 20 October 2021

External

Internal

Overview

Prim's algorithm is a greedy algorithm that computes the minimum cost spanning tree (MST) of a an undirected graph. Even if the algorithm was named after Prim, it was discovered earlier by Jarník. The algorithm is similar to Dijkstra's shortest-path algorithm.

The running time of optimized implementation of the Prim's algorithm is O(m log n).

Non-Optimized Implementation

The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a greedy algorithm.

 Initialize X={s} # X is the set of vertices that we spanned so far, s ∈ V chosen arbitrarily
 Initialize T=∅ # T is the minimum spanning tree built so far. Invariant: X = vertices spanned by the three-so-far T 
 while X ≠ V: # The main loop, each iteration grows X with one node
     let e=(u,v) be the cheapest edge of G with u ∈ X, v ∉ X
     add e to T
     add v to X

Correctness Proof

The Prim's algorithm always computes a MST.

https://www.coursera.org/learn/algorithms-greedy/lecture/15UXn/correctness-proof-i
https://www.coursera.org/learn/algorithms-greedy/lecture/hYzal/correctness-proof-ii

Add summary here.

Optimized Implementation

The optimized implementation uses heaps, in a similar manner to Dijkstra's shortest-path algorithm.

https://www.coursera.org/learn/algorithms-greedy/lecture/bYMq1/fast-implementation-i
https://www.coursera.org/learn/algorithms-greedy/lecture/qzdR8/fast-implementation-ii

Add summary here.