Prim’s Algorithm: An Intuitive Understanding

Prim :)

Ok… this will be a short article. It’s more similar to a short post but I wanted to put this out there so people can know about it.

So… Prim’s Algorithm. I was a little confused about Prim’s Algorithm. It has a very simple procedure but the intuition (at least for me) was quite difficult to grasp. In this article, I will try and intuitively explain Prim’s.

Prim’s Algorithm: A Short Summary

This article isn’t for explaining how Prim’s Algorithm works, it’s more for the intuition but here’s a short recap of how it works:

Prim’s Algorithm is a method to find the MST (Minimum Spanning Tree) of a graph. The MST is basically a subset of a graph G that has the lowest sum of weights but must connect all vertices of G.

Prim’s Algorithm does this by initializing a MST with a randomly selecting root node in the original graph. From this root node, it considers the neighbour vertices and selects the one with the shortest path to the root. It adds the vertex and the path to the MST.

Prim’s then considers all paths from all of the MST’s vertices to their neighbours and selects a neighbour based on it having the shortest path to a MST vertex. The vertex and the shortest path from it to any MST vertex are added to the MST. This continues until all vertices of the original graph are added to the MST.

Intuition behind the Prim’s Algorithm:

So what is the intuition?

Consider this diagram:

If you can only draw lines from dot to dot, how would you find the shortest path connecting all dots?

Well, it’s simple:

Select a root dot. Find the dot with the shortest distance to the root dot. Draw a line between these dots. Then, select a dot with the shortest distance to any of the points on the line. (obviously, excluding the points already in the line) Then, connect the selected dot to the closest dot already in the line. Repeat this until all dots are connected. The line drawn would then look like this:

The intuition behind this procedure is the same as how Prim’s finds the MST of a graph:

NOTE: In terms of equivalent terminology, dot is the equivalent of vertex, distance is just weighted path)

Ok, now there’s only one more thing to understand.

Prim’s basically selects the nearest neighbours to MST vertices. Why does it ignore other vertices??

Consider the graph bellow:

The weighted path or distance from A-C will always be greater than the weighted distance of distance from A-B. (as long as the weights are non-negative) Indeed, immediate neighbours to any given node of a non-negative graph will always have a shorter weighted path to said node than non-neighbour nodes.

This means when Prim’s is trying to find the vertex with the shorter weighted path to any MST vertices, it can ignore vertices which aren’t immediate neighbours to existing MST vertices because they will have greater weighted paths to the MST vertices.

Thanks for listening to my rambling that is a Medium article. If you know of a simpler way to understanding the intuition of Prim’s, please do leave a comment or email me at martintin@rogers.com.

If you’re interested, here is my Prim’s Algorithm implementation (in Java)

public class SPT {
    int[][] graph;
    int V; 
    //initializes tree graph
    public SPT(int v){
        this.V = v;
        this.graph = new int[this.V][this.V];
    }
    //finds nearest vertex to Minimum Spanning Tree (not including vertices already part of the MST)
    public int minDist(int[] dist, Boolean[] SPT){
        int minDist = Integer.MAX_VALUE, minIndex = -1;
        for(int v=0;v<this.V;v++){
            if(!SPT[v] && dist[v] < minDist){
                minIndex = v;
                minDist = dist[v];
            }
        }
        return minIndex;
    }
    //prints the MST 
    public void printSPT(int[] dist, int[] parent){
        System.out.println("Edge:\tWeight:");
        for(int v=1;v<this.V;v++){
            System.out.println(parent[v]+"-"+v+"\t"+dist[v]);
        }
    }
    //adds path between a to b to graph tree
    public void addPath(int a, int b, int w){
        this.graph[a][b] = w;
        this.graph[b][a] = w;
    }
    // does Prim's algorithm on constructed tree
    public void Prims(){
        Boolean[] SPT = new Boolean[this.V];
        int[] dist = new int[this.V];
        int[] parent = new int[this.V];
        for(int v=0;v<this.V;v++){
            SPT[v] = false;
            dist[v] = Integer.MAX_VALUE;
        }
        dist[0] = 0;
        parent[0] = 0;
        
        for(int i=0;i<this.V;i++){
            int u = minDist(dist,SPT);
            SPT[u] = true; 
            for(int v=0;v<this.V;v++){
                if(!SPT[v] && graph[u][v] > 0 && graph[u][v]+dist[u] < dist[v]){
                    parent[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }
        printSPT(dist,parent);
    }