Home » DAA | Kruskal Algorithm

DAA | Kruskal Algorithm

by Online Tutorials Library

Kruskal Algorithm

The Kruskal Algorithm is used to find the minimum cost of a spanning tree. A spanning tree is a connected graph using all the vertices in which there are no loops. In other words, we can say that there is a path from any vertex to any other vertex but no loops.

What is Minimum Cost Spanning Tree?

The minimum spanning tree is a spanning tree that has the smallest total edge weight. The Kruskal algorithm is an algorithm that takes the graph as input and finds the edges from the graph, which forms a tree that includes every vertex of a graph.

Working of Kruskal Algorithm

The working of the Kruskal algorithm starts from the edges, which has the lowest weight and keeps adding the edges until we reach the goal.

The following are the steps used to implement the Kruskal algorithm:

  • First, sort the edges in the ascending order of their edge weights.
  • Consider the edge which is having the lowest weight and add it in the spanning tree. If adding any edge in a spanning tree creates a cycle then reject that edge.
  • Keep adding the edges until we reach the end vertex.

Let’s understand through an example.

Consider the below graph.

DAA Kruskal Algorithm

Now we have to calculate the minimum spanning tree of the above graph. To find the minimum cost spanning tree, the first step is to remove all the loops and the parallel edges from the graph. Here, parallel edges mean that there exists more than one edge between the two vertices. For example, in the above graph, there exists two edges between the vertices A and B having weights 5 and 10 respectively, so these edges are the parallel edges. We have to remove any of the edges.

In case of parallel edges, the edges with the highest weight will be removed. In the above graph, if we consider the vertices A and B then the edge with a weight 10 is more than the edge with weight 5 so we discard the edge having weight 10. So, we remove the edge having weight 10 as shown as below:

DAA Kruskal Algorithm

Once we remove the parallel edge, we will arrange the edges according to the increasing order of their edge weights. As we can observe in the above graph, the minimum edge is 2. There are two edges having weight equals to 2 which can be written as:

BD = 2

DE = 2

The next minimum edge weight is 3. There are two edges with a weight 3 so it can be written as:

AC = 3

CD = 3

The next edge with a minimum weight is 4. There is only one edge having weight 4 and it can be written as:

BE = 4

The next edge with a minimum weight is 5. There is only one edge having weight 5 and it can be written as:

AB = 5

The next edge with a minimum weight is 6. There is only one edge having weight 6 and it can be written as:

CB = 6

The next edge with a minimum weight is 7. There is only one edge having weight 7 and it can be written as:

AF = 6

The next edge with a minimum weight is 8. There is only one edge having weight 8 and it can be written as:

FC = 6

Once the edge weights are written in the increasing order, the third step is to connect the vertices according to their weights. The edge weight 2 is minimum, so we connect the vertices with a edge weight 2 as shown as below:

DAA Kruskal Algorithm

The next edge is AC having weight 3 shown as below:

DAA Kruskal Algorithm

The next edge is CD. If we connect the vertices C and D then it does not form any cycle shown as below:

The next edge is BE. But we cannot connect the vertices B and E as it forms a cycle.

The next edge is AB. But we cannot connect the vertices A and B as it forms a cycle.

The next edge is BC. But we cannot connect the vertices B and C as it forms a cycle.

The next edge is AF. If we connect the vertices A and F then it does not form any cycle shown as below:

DAA Kruskal Algorithm

Algorithm

Implementation of kruskal’s algorithm in C++

Output

DAA Kruskal Algorithm


Next Topic#

You may also like