Prim's Algorithm: Difference between revisions
| Line 9: | Line 9: | ||
=Overview= | =Overview= | ||
Prim's algorithm is a [[Algorithms#Greedy_Algorithms|greedy algorithm]] that computes the [[The_Minimum_Spanning_Tree_Problem|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%27s_Shortest-Path_Algorithm|Dijkstra's shortest-path algorithm]] in that it iterates over the all nodes of the graph, one node at a time, and then evaluates | Prim's algorithm is a [[Algorithms#Greedy_Algorithms|greedy algorithm]] that computes the [[The_Minimum_Spanning_Tree_Problem|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%27s_Shortest-Path_Algorithm|Dijkstra's shortest-path algorithm]] in that it iterates over the all nodes of the graph, one node at a time ("growing like a mold, from a starting point"), and then evaluates all edges that cross the cut formed by the explored territory and the unexplored territory, attempting to find the cheapest edge. The cost of the edge is the [[Algorithms#Greedy_Score|greedy score]]. There is a [[#Non-Optimized_Implementation|non-optimized implementation]], where all possible edges are evaluated at each step, and whose running time is O(m n), and an [[Prim%27s_Algorithm#Optimized_Implementation|optimized implementation]] that uses heaps, whose running time is O(m log n). | ||
=Non-Optimized Implementation= | =Non-Optimized Implementation= | ||
Revision as of 22:31, 21 October 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/tQ6gK/prims-mst-algorithm
- https://en.wikipedia.org/wiki/Prim's_algorithm
Internal
- Graph Concepts
- The Minimum Spanning Tree Problem
- Dijkstra's Shortest-Path Algorithm
- Greedy Algorithms
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 in that it iterates over the all nodes of the graph, one node at a time ("growing like a mold, from a starting point"), and then evaluates all edges that cross the cut formed by the explored territory and the unexplored territory, attempting to find the cheapest edge. The cost of the edge is the greedy score. There is a non-optimized implementation, where all possible edges are evaluated at each step, and whose running time is O(m n), and an optimized implementation that uses heaps, whose running time 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
Playground Implementation
Correctness Proof
The Prim's algorithm always computes a MST.
Add summary here.
Optimized Implementation
The optimized implementation uses heaps, in a similar manner to Dijkstra's shortest-path algorithm.
Add summary here.