Prim's Algorithm for Minimum Spanning Tree

Prim's Algorithm

Overview

• A greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected, and weighted graph.
• It is an efficient solution for finding the MST in a graph with non-negative edge weights.

How it Works

1. Choose a starting node: Select an arbitrary node from the graph as the starting point.
2. Initialize the MST: Create an empty minimum spanning tree and add the starting node to it.
3. Grow the MST: In each iteration, select the edge with the minimum weight that connects a node in the MST to a node not in the MST.
4. Add the edge and node: Add the selected edge and node to the MST.
5. Repeat until complete: Continue growing the MST until all nodes in the graph are included.

Key Properties

• Time Complexity: O(|E|log|V|) using a binary heap, where |E| is the number of edges and |V| is the number of vertices.
• Space Complexity: O(|V| + |E|) to store the graph and the MST.

Example

Suppose we have a graph with nodes A, B, C, and D, and edges with weights as follows:

A --2--> B
|    / |    |
| 3 /  | 4  |
|/    |    |
C --5--> D

Applying Prim's algorithm, we can find the MST as follows:

1. Start with node A.
2. Add edge AB (weight 2) and node B to the MST.
3. Add edge BC (weight 3) and node C to the MST.
4. Add edge CD (weight 5) and node D to the MST.

The resulting MST is:

A --2--> B --3--> C --5--> D