How does Prim's algorithm work?

Overview

Prim's Algorithm is an algorithm that takes a weighted undirected graph as an input and outputs its Minimum Spanning Tree (MST). At every step, it selects an open edge that has the minimum weight.

Note: The nodes in the graph must have no self-loops, and there should be no parallel edges.

Algorithm Steps

1. Randomly select a node as the root node and mark it as visited. Open all edges associated with the root node.
2. From the opened edges, select the edge with the minimum weight. In case there are multiple edges with the same minimum weight, select any one.
3. If both nodes in the selected edge are already marked visited, close that edge and go to step 2 again. Otherwise, continue to the next step.
4. Add the selected edge to the MST and mark the edge nodes as visited. Open all closed edges associated with the visited nodes.
5. If all edges are marked visited, terminate the algorithm. Otherwise, repeat step 2.

Example

Consider the graph above. Let’s run Prim’s algorithm on it.

Step 1a

Any node can be the root node. Let's go with node A as our root node and mark it as visited.

Step 1b

The edges associated with node A are opened. These include A-B, A-D, and A-C.

Step 2a

From the opened edges, the edge with the minimum weight A-D is added to the MST and D is marked as visited.

Step 2b

The edges D-B, D-E, and D-G are opened because of their association with node D.

Step 3a

The opened edge with the least weight, such as nodes, D-B is added to the MST and node B is marked as visited.

Step 3b

The only closed edge of node B, B-E is opened.

Step 4a

Two open edges have the minimum weight. Both B-E and D-E can be added to the MST. In this case, B-E was added to the MST and node E was marked as visited.

Step 4b

The edge E-G is opened.

Step 5a

E-G has the minimum weight among the opened edges so it is added to the MST. Node G is marked as visited.

Step 5b

The minimum weight edge is now D-E, but both D and E have been marked visited. Hence, the edge will be closed.

Step 6a

G-F, A-B and D-G all have the minimum weight. G-F is added to the MST and F is marked as visited.

Step 6b

F-C is opened because it is the last edge of E that is not opened.

Step 6c

The nodes in the minimum weight edge A-B are already visited. Therefore, it is closed.

Step 6d

Again, the nodes in the minimum weight edge D-G are already visited, thats why it is closed.

Step 7

The minimum cost edge F-G is added to the MST and node C is marked visited. As all of the nodes have been visited, the algorithm stops.

Result

Time complexity

The time complexity of Prim's algorithm is O(E log V) if a min-heap is used. Here, V is the number of vertices and E is the number of edges.

Space complexity

The space complexity of Prim's Algorithm is O(E+V). Here, V is the number of vertices and E is the number of edges.