Prim's Algorithm

Introduction

You have a new government contract for painting the roads connecting major cities but you are on a very tight budget. You have to do this task using the minimum paint possible so there should be one and only one painted road connecting any two cities.

To accomplish this we need to find all the roads that if chosen would take the least amount of paint and still connect every city. Introducing Prim's Algorithm.

What is Prim's Algorithm?

Suppose you are given a graph and are asked to convert it to a tree such that when we sum all the weights of the tree it is minimum from all other possible trees. Such a tree is called a minimum spanning tree and we can use Prim's algorithm to find it.

How Prim's Algorithm Works?

The algorithm works by iteratively adding vertices to the MST, starting from a given source vertex.

Here are the step-by-step workings of Prim's algorithm:

Step 1: Initialize the MST

The algorithm starts by initializing the MST with a single vertex, which can be any vertex of the graph.

Step 2: Identify the minimum weight edge

The algorithm then identifies the minimum weight edge that connects a vertex in the MST to a vertex outside the MST. This edge is added to the MST.

Step 3: Update the set of candidate edges

The algorithm updates the set of candidate edges that connect vertices in the MST to vertices outside the MST. This set is updated by considering all edges that connect vertices in the MST to vertices outside the MST, and removing any edges that would create a cycle in the MST.

Step 4: Repeat until the MST is complete

Steps 2 and 3 are repeated until all vertices of the graph are included in the MST. In each iteration, the algorithm identifies the minimum weight edge that connects a vertex in the MST to a vertex outside the MST, and adds it to the MST. The set of candidate edges is updated to remove any edges that would create a cycle in the MST.

Prim's Algorithm Implementation

Prims Algorithm belongs to the Greedy class of algorithms. This simply means that at every step, the algorithm will make a decision depending on what is the best choice at that point.

In other words at each step, it solves the current problem in the best way and assumes the complete problem will be solved eventually in the best way.

Let's take a look at the steps of the algorithm:

1. Start with a random vertex in the graph and mark it as visited
2. Iterate over all the visited vertices and pick the minimum weight edge that is not yet processed
3. Keep repeating step 2 until all the nodes are visited.

The below graphic shows Prims algorithm in action. The blue line at each step is the smallest edge of all the edges connected to the current set of vertices.

Prim's Algorithm Example

Let’s see a step-by-step walkthrough of the algorithm:

Consider the below table with all source and destination vertices along with their weights. We want to find the minimum spanning tree for this graph.

We can represent this table in the form of a diagram as shown in the first figure below:

Figure-1: We pick a random vertex (A in our case). The smallest edge from A is AF having a weight of 3.

Figure-2: Now A and F are the vertices in our answer set. The edges for these vertices which are not yet selected are (AB, AC, and FE). Of these FE has the smallest weight of 3.

Figure-3: Now the answer set has A, F, and E. Among the edges connected to all these vertices, EC has the next minimum cost.

Figure-4: Vertices A, F, E, and C are visited. The not selected edges for these vertices are CB, CA, AB, CD, ED. Of these, edge CB has the minimum cost.

Figure-5: The next minimum cost edge is CD.

Figure-6: We stop the algorithm as all the vertices are visited.

Prim's Algorithm Pseudocode

Java and C++ Examples

1. Java

2. C++

Prim's Algorithm Time Complexity

The adjacency matrix implementation we saw before uses a nested for loop in findMST() function that goes from $0$ to $V$. Hence the time complexity would be $O(V^2)$. This can be further reduced depending on the data structure we use for implementing the algorithm.

Using a binary heap to store the vertices of the input graph ordered by weight will improve the time to select the minimum weight vertex at every step.

The Fibonacci heap is a complicated but efficient version of the heap(better insertion times) which can further improve the complexity but makes the implementation difficult.

The below table summarizes the time complexities for different data structures used for representing the graph and ordering the edges corresponding to visited vertices.

Difference between Prims and Kruskal Algorithm

Both Prim and Kruskal follow the greedy approach. The difference is, Prim's greedily chooses vertices while Krushkal's greedily chooses edges.

In Kruskal, we sort through the edges first so that we can select them later one by one from minimum to maximum. This sorting is a costly operation.

Prim's on the other hand goes vertex by vertex only considering edges with minimum cost. So Prim's does not have to worry even if the number of edges increases as it is never going to process every edge.

Hence, Prims Algorithm is better than Kruskal's when the graph is dense. i.e. the number of edges is close to the maximal number of edges possible.

Prim's Algorithm Applications

1. Maze generation: For a randomly weighted graph prims algorithm can be used to generate a maze. Any two nodes can act as the entry and exit nodes of the maze.

2. Cable laying, electric grids layout, LAN networks, especially cases where the graphs are dense - In these cases, we need to find connect all the nodes while ensuring the minimum amount of cable is being used exactly the problem statement for Prim's algorithm.

Prim's Mantra

Keep the best(minimum cost) edge for every vertex.