Prim’s and Kruskal’s Algorithm

An overview of two of the most popular greedy algorithms

Have you ever used Google Maps for directions? Have you ever used social media apps like Facebook or Instagram? Well, guess what, you have been using graphs all along. Let’s see what these algorithms actually are and how they work!

What is Minimum Spanning Tree?

In a graph with weighted edges, a minimum spanning tree is a subgraph or a spanning tree that has lesser weight than all other spanning trees of the same graph. In real-life examples, this weight can be measured as distance, length or any arbitrary value denoted to the edges.

Basically it is a subgraph of a main graph which contains all the vertices from the main graph, the vertices are connected and there are no cycles or loops.

Why is it called Greedy Algorithm?

It is called greedy because it chooses the optimal solution present at the moment and not the optimal solution as a whole. In greedy algorithms, at every step, there is a choice that is optimal for the problem up to that step, and after the last step, the algorithm produces the optimal solution of the complete problem.

How to find cost of Minimum Spanning Tree?

The cost of the spanning tree is simply the sum of the weights of all the edges in the tree. There are usually more than one spanning tree. Minimum spanning tree is the spanning tree where the cost is the least among all the spanning trees. There also can be more than one minimum spanning tree.

In simple words, in a minimum spanning tree, sum of weight of edges should be minimum and all vertices should be connected. For n number of vertices in the weighted graph, the number of edges in the minimum spanning tree will be n-1.

Kruskal’s Algorithm Working

Let’s understand how to find the cost of the minimum spanning tree using Kruskal’s algorithm with an example.

Here we have an undirected graph with weighted edges and 7 vertices. To start with Kruskal’s algorithm we take the 7 vertices and no edges.

We see all the options we have to join edges and keep joining the minimum weighted edges until it creates cycles or loops.

We can see that the minimum weighted edge is 1, that is edge DB and FG. So we connect them.

We can see that the minimum weighted edge is 2, that is edge AB and DE. So we connect them.

We can see that the minimum weighted edge is 3, that is edge BE. But can we connect it? NO. This is because it creates a cycle between B,D and E.

We can see that the minimum weighted edge is 4, that is edge AD. But can we connect it? NO. This is because it creates a cycle between A,D and B.

We can see that the minimum weighted edge is 4, that is edge BG. So we connect them.

We can see that the minimum weighted edge is 5, that is edge AF. But can we connect it? NO. This is because it creates a cycle between A,F,G and B.

We can see that the minimum weighted edge is 6, that is edge GC. So we connect them.

Now, all the vertices are connected and thus we can stop. This is the minimum spanning tree and we can find its cost by adding the weights of the edges, which is 16. So this was how Kruskal’s algorithm works.

Prim’s Algorithm Working

Let’s understand how to find the cost of the minimum spanning tree using Prim’s algorithm with an example.

Here we have an undirected graph with weighted edges and 7 vertices. To start with Prim’s algorithm we take the 7 vertices and no edges.

Here the approach is quite different. We choose one vertex to start from and the adjacent vertices are taken in as options to connect edges and we connect the minimum weighted edge until we create loops or cycles. For example, we choose A, now D,B and E are options for making an edge.

We connect the least weighted edge possible out of the given options, which is 2, from A to B.

Now since B is a chosen vertex, all the adjacent vertices are options. D,E,C,G and F are options for edges.

We connect the least weighted edge possible out of the given options, which is 1, from D to B.

Now since D is a chosen vertex, E is also an option.

We connect the least weighted edge possible out of the given options, which is 2, from D to E.

Out of the given options, the minimum weighted edge is 3 which is edge BE. But can we connect it? NO. This is because it creates a loop between the vertices B,D and E.

We connect the least weighted edge possible out of the given options, which is 4, from B to G. Edge AD is not connected as it creates a cycle.

Since G is now a chosen vertex, C and F are options now.

We connect the least weighted edge possible out of the given options, which is 1, from F to G.

Out of the given options, the minimum weighted edge is 5, which is edge AF. But can we connect it? NO. This is because it creates a loop.

We connect the least weighted edge possible out of the given options, which is 6, from C to G.

Now, all the vertices are connected and thus we can stop. This is the minimum spanning tree and we can find its cost by adding the weights of the edges, which is 16. So this was how Prim’s algorithm works.

Pseudocode for Prim’s Algorithm

First, we create a null set A, where we will add all the edges of the minimum spanning tree. Then we create two sets of vertices U and V-U. V-U the list of vertices that haven’t been visited and U contains the list of vertices that have been visited. We move vertex by vertex, and move vertices from set V-U to set U by connecting the least weighted edge.

A = ∅;
U = {1};
while (U ≠ V)
    let (u, v) be the least weighted edge such that 
    v ∈ V - U and u ∈ U;
    A = A ∪ {(u, v)}
    U = U ∪ {v}

Pseudocode for Kruskal’s Algorithm

First, we create a null set A, where we will add all the edges of the minimum spanning tree. Then we will find out if an edge creates a cycle or not. The most common way to find this out is an algorithm called Union find, which divides the vertices into groups and checks if two vertices belong to the same group or not and decides whether adding an edge creates a loop. If it does not create a cycle, it is added into the set A.

A = ∅
For each vertex v ∈ V:
    add to set V
For each edge (u, v) ∈ E ordered by weight(u, v):
    if u ≠ v:       
    A = A ∪ {(u, v)}
    union find(u, v)
return A

Real Life Applications

We have been using graphs and these algorithms in daily life and we didn’t even know. Here are some examples where Prim’s and Kruskal’s are used and are absolutely essential for us:

1. Network topologies (LAN)

2. Google Maps

3. Social Networking

4. Electric grids

Data Structure & Algorithms - Spanning Tree

Greedy Algorithms | Brilliant Math & Science Wiki

Minimum Spanning Tree Tutorials & Notes | Algorithms | HackerEarth

Kruskal's Algorithm

Prim's Algorithm