Prims Algorithm for Minimum Spanning Tree Analysis
Algorithm:
Graph:
(Note: Missing edge weight, (T, Y, 8))
Before the first iteration:
The min priority Queue(min key at start)
Q = [(S, 0), (T, ∞), (X, ∞), (Y, ∞), (Z, ∞)]
Iteration 1:
U = S
Q = [(T, 6), (Y, 7), (X, ∞), (Z, ∞)]
Updates Keys of T and Y
Iteration 2:
U = T
Q = [(Z, -4), (X, 5), (Y, 7)]
Updates Keys of X, Y, Z
Iteration 3:
U = Z
Q = [(X, 5), (Y, 7)]
No updates
Iteration 4:
U = X
Q = [(Y, 7)]
No updates
Iteration 5:
U = Y
Q = []
No updates
Queue empty, loop terminates
We have the following edges in our minimum spanning tree:
(S, T, 6), (T, Z, 5), (T, Z, -4), (S, Y, 7)
Cost = 6 + 5 - 4 + 7 = 14
This is obviously not a MST because we have other trees with lesser cost,
(S, Y, 7), (Y, X, -3), (X, T -2), (T, Z, -4)
Cost = 7 - 3 - 2 - 4 = -2
Please help me identify where I have gone wrong.
For reference: (Please ignore the red edges)
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.