Prim’s and Kruskal’s Algorithm

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.

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.

Kruskal’s Algorithm Working

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

Prim’s Algorithm Working

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

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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store