Mohammed Ashfaq Ashar for Mozilla Club of UCSC

Posted on Jan 13, 2021 • Edited on Jan 15, 2021

Kruskal's and Prim's algorithm

#algorithms #tutorial #tree

Today I have come with an interesting tutorial which is Krushkal’s and prim's algorithm. First of all, I would like to explain to you all about the definition of Data structure and Algorithm. The data structure is considered as the way to organize and store data and information in an efficient way such that you can access them quickly, whereas algorithms are considered as the steps that have to be taken to get the expected output from a given set of inputs.
According to research, many computer science students have facing difficulties to understand Data structure and Algorithm, due to the complexity of the subject. Even though it is hard to understand, it plays a major role in the IT industry.
So, in today’s blog, I would like to give you a brief and clear explanation of Kruskal’s and Prim's algorithm which is widely used in finding a minimum spanning tree. I hope you all have a better foundation in trees and minimum spanning trees. However, I would like to explain this algorithm with all the basic explanations of trees and minimum spanning trees from scratch.
Now let us begin

What are trees?

From the above figure, I hope you have got some ideas regarding the definition of a tree. Simply, we can say the tree is a collection of edges and vertices. There are several types of trees where each tree has its unique functionalities. Some of the trees are

Binary tree
Red black tree
Binary search tree
AVL tree
B tree

and so on.
As I mentioned before, trees are classified into a variety of types due to their functionalities. Some of the functionalities are

Used to hierarchical data
Used to implement expression parsers and expression solvers.
Used the Memory management subsystem of the Linux kernel to search memory regions of processes during preemption.

and so on.

I hope now you have got a better foundation about the definition and uses of Trees. Now let us see what spanning and minimum spanning tree
Initially let us look at spanning tree

What is a Spanning tree?

As simply we can say that a spanning tree is a subgraph of an undirected graph, where it consists of all the vertices with a minimum number of edges.
Let's take an example,
Here there is an undirected graph, we have to find the spanning tree of it.

So initially, we have mentioned all the vertices. Then we have connected them by edges, such that the number of edges is minimum. And here, since it is a tree, there should be any cyclic formation. So as a final output, the spanning tree will look like

There may be several spanning trees we can get from a given undirected graph. As to make this simple, I have given only one spanning tree.

This is the complete idea of a spanning tree. I hope you have got some idea about the spanning tree. As a next step, lets us look at the minimum spanning tree, where we are going to learn about Kruskal’sand prim's algorithm

What is the Minimum spanning tree?

The minimum spanning tree is a spanning tree, where the addition or the sum of the weight of the edges should be minimum.
I hope you all are wondering, why we have to find the minimum spanning tree, and what is the use

Ok, to clear this issue I would like to give you some practical usage of minimum spanning tree.
It is heavily used in

Network design such as telephone and cable networks.
Traveling salesman problem
Cluster analysis
Entropy-based image registration and so on

Now comes, a big question

How to find a minimum spanning tree from a given undirected graph?
Is there any technique for it?
How to apply it?

Here the place where Kruskal’s and prim's algorithm comes into play. From all the above information you have got some solid idea about trees, spanning trees, minimum spanning trees, and their applications. Now let us discuss this algorithm

How to find Minimum Spanning Tree?

We have two approaches to find the minimum spanning tree. Simply, these 2 approaches are algorithms. They are

Kruskal’sAlgorithm
Prim's Algorithm

Here I am going to explain the above two algorithms thoroughly with example.
Let's look at our 1st algorithm which is the Kruskal's algorithm

Kruskal’s Algorithm

This is one approach that we can use to find the minimum spanning tree.
I don’t like to provide algorithm at once so that you won’t get a better understanding. Rather, I would like to provide you with a pictorial example so that you will have a complete picture of this algorithm very clearly

Let’s look at our example

Find the minimum spanning tree of the graph below

Step 1

Arrange all the edges in ascending order according to their weight( the value is written on top of the edge). Src means starting vertex and Dest means ending vertex

Step 2

Now we shall pick the shortest weight out of all

Step 3

Keep in mind, there should be no cycle. So we pick the next short one which is 8 - 2

Step 4

Pick next short one 6 – 5

Step 5

Pick the next short one which is 0 – 1

Step 6

Pick the next short one which is 2 – 5

Step 7

Now the problem comes. The next short one is 8 – 6 which contains a cycle if we add. So we simply discard it

Step 8

Pick the next short one which is 2 – 3

Step 9

Pick 7 – 8. It will result in a cycle. So simply remove it

Step 10

Pick the next short one which is 0 – 7

Step 11

Pick 1 – 2. It results in the cycle. So discard it

Step 12

Pick the next short one which is 3 – 4 This is the final output. Because all the vertices are present in it and also some of the weight is minimum.

Now we shall have a look into the Prism algorithm to find a minimum spanning tree

Prim's Algorithm

This is another approach that we could follow to obtain the minimum spanning tree.
Let’s take the previous example here itself

I hope that you can remember the above diagram. This is the same one we have taken before for Kruskal’s algorithm
Let’s see how to find the minimum spanning tree by using this approach

In this algorithm, we are free to select any vertex as you wish. So to make this algorithm simpler, I am going to select the starting vertex “0”

Step 1

Select the node/ vertex as the starting node (“0”) and color with green. Then find all the adjacent vertex of it. Put their weight on the adjacent nodes at the same time make “0” as the weight of the starting node.

Step 2

We can observe that weight of 0 – 1 is “4” while 0 – 7 is “8”. We have selected the lowest weight edge, which is 0 – 4. Since we already found the adjacent node of “0”, now we have to find all the adjacent nodes of “1” and connect it.

Step 3

We can observe that vertex “7” and vertex “2” have the same weight. We can select any node as per our wish. I am going to select vertex “7” and color it green after finding all the adjacent vertex of “7” and connecting them

Step 4

Now we can observe that vertex “6” has the lowest weight among vertex “8” and “2”. To find all the adjacent nodes of it and make the vertex “6” with green. We can see that vertex “8” has weight 7 from vertex “7” while from vertex “6” to vertex “8” it weighs “6”. Since we need minimum weight, we break the edge 8 – 7 and connect 6 – 8

We repeat all the steps as mentioned above, finally, we would able to receive output as where all the nodes are in green color

Now I hope you all got a clear understanding of Kruskal’s and prim's algorithm. You are given the freedom to use any two algorithms to find a minimum spanning tree. Some of us feel Kruskal’s algorithm is easier compared to prim's whereas some others feel the prism algorithm is better than Kruskal’s algorithm.
Therefore I have included both the algorithms here so that you are able to get a good understanding of finding a minimum spanning tree.

See you in our next blog!