Member-only story
Minimum spanning tree: Prim’s algorithm
Table of Contents
· 1. What is a minimum spanning tree (MST)?
· 2/ Prim’s algorithm key idea
· 3. Prim’s algorithm efficiency
· 3.1. Simple implementation using adjacency list/matrix:
· 3.2. Implementation using a Priority Queue
· 4. Prim’s algorithm implementation
1. What is a minimum spanning tree (MST)?
A MST is a subgraph of a connected, undirected and weighted graph that fulfills three criteria:
a/ There is no cycle in MST
b/ Connectivity: It connects all vertices in the graph
c/ Minimum total weight: A MST must have the lowest sum of edge weights
2/ Prim’s algorithm key idea
Prim’s algorithm is a greedy algorithm that relies on making locally optimal choices at each step with the belief that this will lead to a globally optimal solution. The key idea of Prim’s algorithm is to iteratively expand a growing tree by adding the cheapest edge that connects an existing vertex in the tree to a new vertex that not yet included. Below are the steps of Prim’s algorithm:
