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

  Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.    Step 2: Create a set E that contains all the edges of the graph.    Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning    Step 4: Remove an edge from E with minimum weight    Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F     (for combining two trees into one tree).    ELSE    Discard the edge    Step 6: END    

Implementation of kruskal’s algorithm in C++

  #include       #include       using namespace std;      const int MAX = 1e4 + 5;      int id[MAX], nodes, edges;    // variables declaration  pair  > p[MAX];      void init()      {          for(int i = 0;i < MAX;++i)              id[i] = i;      }        int root(int x)      {          while(id[x] != x)          {              id[x] = id[id[x]];              x = id[x];          }          return x;      }        void union1(int x, int y)      {          int p = root(x);          int q = root(y);          id[p] = id[q];      }       // function to find the minimum cost spanning tree  long long kruskal(pair > p[])      {          int x, y;          long long cost, minimumCost = 0;          for(int i = 0;i < edges;++i)          {              x = p[i].second.first;             y = p[i].second.second;              cost = p[i].first;              if(root(x) != root(y))              {                  minimumCost += cost;                  union1(x, y);              }              }          return minimumCost;      }       int main()      {          int x, y;          long long weight, cost, minimumCost;          init();          cout <<“Enter Nodes and edges”;          cin >> nodes >> edges;          for(int i = 0;i < edges;++i)          {              cout<<“Enter the value of X, Y and edges”;          cin >> x >> y >> weight;              p[i] = make_pair(weight, make_pair(x, y));          }          sort(p, p + edges);          minimumCost = kruskal(p);          cout <<“Minimum cost is “<< minimumCost << endl;          return 0;      }  

Output

DAA Kruskal Algorithm

Next Topic#

DAA | Kruskal Algorithm

Kruskal Algorithm

What is Minimum Cost Spanning Tree?

Working of Kruskal Algorithm

Algorithm

Implementation of kruskal’s algorithm in C++

SQL Interview Questions (2022)

Bridge Pattern

You may also like