Q2Design and Analysis of Algorithms
Question
Describe Prim's Algorithm for Minimum Spanning Tree with an example.
Answer
Prim's algorithm grows the MST from a starting vertex by repeatedly adding the minimum-weight edge connecting the tree to a new vertex.
Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) by starting from an arbitrary vertex and repeatedly adding the minimum-weight edge that connects a vertex in the MST to a vertex outside it.
- Initialize: key[source] = 0, key[all others] = ∞. Add all vertices to a priority queue. parent[] array tracks MST structure.
- While priority queue is not empty: extract vertex u with minimum key value.
- For each neighbor v of u not yet in MST: if weight(u,v) < key[v], update key[v] = weight(u,v) and parent[v] = u.
- Repeat until all vertices are in the MST.
Graph with vertices A,B,C,D and edges A-B(4), A-C(2), B-C(1), B-D(5), C-D(8). Start at A: Add A-C(2), then C-B(1), then B-D(5). MST has edges {A-C, B-C, B-D} with total weight 8.
Time Complexity: O((V+E) log V) with a binary heap. O(E log V) for dense graphs. Unlike Kruskal's (edge-based), Prim's grows the tree vertex by vertex, making it more suitable for dense graphs.