Implementation Idea
Prim’s algorithm can be implemented in different ways, but the core idea is always the same: keep track of the cheapest edge that can connect each outside vertex to the current tree.
Instead of repeatedly inspecting the whole graph manually, we usually store candidate vertices in a priority queue ordered by their current cheapest connection cost.
Data Structures
A common implementation uses:
- key[v]: cheapest known cost to connect vertex v to the tree;
- parent[v]: the vertex that connects v to the MST;
- visited[v]: whether v is already inside the tree;
- priority queue: stores vertices ordered by their current key value.
At the end, the parent array describes the minimum spanning tree.
Pseudocode
Prim(G, start):
for each vertex v in G:
key[v] = infinity
parent[v] = null
visited[v] = false
key[start] = 0
priorityQueue.insert(start, 0)
while priorityQueue is not empty:
u = priorityQueue.extractMin()
if visited[u]:
continue
visited[u] = true
for each edge (u, v) with weight w:
if not visited[v] and w < key[v]:
key[v] = w
parent[v] = u
priorityQueue.insert(v, key[v])
return parentThe algorithm repeatedly chooses the next cheapest vertex to add and updates the best known connection cost for its neighbors.
How to Read the Pseudocode
The value key[v] represents the best edge found so far to connect vertex v to the growing tree.
When a better edge is found, we update both: key[v] and parent[v].
The priority queue makes sure that the next selected vertex is always the one with the smallest connection cost.
parent[v] tells which edge was chosen to connect v.
Complexity
The time complexity of Prim’s algorithm depends on the graph representation and on the data structure used to choose the next minimum edge.
| Implementation | Typical use case | Time complexity |
|---|---|---|
| Adjacency matrix | Dense graphs | O(V²) |
| Adjacency list + binary heap | Sparse graphs | O((V + E) log V) |
| Adjacency list + Fibonacci heap | Theoretical optimization | O(E + V log V) |
In most practical implementations, an adjacency list with a binary heap priority queue is a very common and efficient choice.
What do V and E mean?
In graph algorithms:
- V is the number of vertices;
- E is the number of edges.
A dense graph has many edges, often close to the maximum possible number. A sparse graph has relatively few edges.
Prim vs Kruskal in Practice
Both Prim and Kruskal find a minimum spanning tree, but they approach the problem from different perspectives.
| Prim | Kruskal |
|---|---|
| Grows one tree from a starting vertex | Sorts edges and merges components |
| Often natural with priority queues | Often natural with Union-Find |
| Focuses on the frontier of the current tree | Focuses on globally sorted edges |
| Can be convenient for connected dense graphs | Can be convenient for sparse edge lists |
Common Mistakes
- Choosing the globally smallest edge instead of the smallest edge leaving the current tree.
- Adding an edge to a vertex that is already inside the tree.
- Forgetting that Prim assumes the graph is connected if we want one spanning tree.
- Confusing the final MST edges with every edge examined by the algorithm.
Final Summary
Prim’s algorithm is a greedy algorithm for finding a minimum spanning tree in a connected, weighted, undirected graph.
It starts from one vertex, grows a single tree, and repeatedly adds the lightest edge that connects the current tree to a new vertex.
Its correctness comes from the cut property, and its efficiency depends on how we represent the graph and choose the next minimum candidate.
Where to Go Next
After studying Prim and Kruskal, a natural next step is to compare minimum spanning tree problems with shortest path problems.
Minimum spanning trees minimize the total cost to connect all vertices. Shortest path algorithms, such as Dijkstra, minimize the cost of paths from one source to other vertices.
These problems look similar at first, but they answer different questions.