Prim's Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
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 [[Algorithms#Greedy_Algorithms|greedy algorithm]]. | 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 [[Algorithms#Greedy_Algorithms|greedy algorithm]]. | ||
<font size=-1> | <font size=-1> | ||
Initialize X={s} <font color=teal># X is the set of vertices that we spanned so far | Initialize X={s} <font color=teal># X is the set of vertices that we spanned so far, s ∈ V chosen arbitrarily</font> | ||
Initialize T=∅ <font color=teal># T is the minimum spanning tree built so far. Invariant: X = vertices spanned by the three-so-far T</font> | |||
Initialize T=∅ <font color=teal># T is the minimum spanning tree built so far | |||
while X ≠ V: <font color=teal># The main loop, each iteration grows X with one node</font> | while X ≠ V: <font color=teal># The main loop, each iteration grows X with one node</font> | ||
let e=(u,v) be the cheapest edge of G with u ∈ X, v ∉ X | let e=(u,v) be the cheapest edge of G with u ∈ X, v ∉ X | ||
Revision as of 22:28, 20 October 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/tQ6gK/prims-mst-algorithm
- https://en.wikipedia.org/wiki/Prim's_algorithm
Internal
Overview
Prim's algorithm is a greedy algorithm that computes the minimum cost spanning tree 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.
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