What is Prim’s algorithm?

Prim’s algorithm is a greedy algorithm i.e., it chooses an optimal path at each point and ultimately finds the shortest path by making a spanning tree.

Algorithm steps

The following steps are used in Prim’s algorithm:

1. Remove all self-loops
2. Remove all parallel edges. If two nodes have a parallel edge, keep the one which has the least cost
3. Select a random node. Check the outgoing edge(s) of that node and pick the edge with the least cost.
4. Check each node until all nodes are visited.

The following illustration explains how Prim’s algorithm works:

Time complexity

The time complexity is

$$O(VlogV + ElogV) = O(ElogV)$$

where V are the vertices and E are the edges of the graph.