Kruskal’s algorithm in C++

In this tutorial, we will learn about Kruskal’s algorithm and its implementation in C++ to find the minimum spanning tree.

Kruskal’s algorithm:

  • Kruskal’s algorithm is an algorithm that is used to find out the minimum spanning tree for a connected weighted graph.
  • It follows a greedy approach that helps to finds an optimum solution at every stage.

Spanning Tree:




  • Spanning Tree is a subset of Graph G, that covers all the vertices with the minimum number of edges.
  • It doesn’t have cycles and it cannot be disconnected.
  • A connected graph may have greater than one spanning tree.
  • The spanning tree is minimally connected. It means, if we remove one edge from the spanning tree then it will make the graph disconnected.

Minimum Spanning Tree (MST) :

  •  it is a spanning tree whose sum of edge weights is smallest among all the spanning trees.

Kruskal's minimum spanning tree in C++

 

Program to implement Kruskal’s algorithm in C++ ( Minimum Spanning Tree )

#include<iostream>
#include<string.h>
using namespace std;

class Graph
{
  char vertices[10][10];
  int cost[10][10],no;
public:
  Graph();
  void creat_graph();
  void display();
  int Position(char[]);
  void kruskal_algo();
};

/* Initialzing adj matrix with 999 */
/* 999 denotes infinite distance */
Graph::Graph()
{
  no=0;
  for(int i=0;i<10;i++)
  for(int j=0;j<10;j++)
  {
 		cost[i][j]=999;
 	}
}

/* Taking inputs for creating graph */
void Graph::creat_graph()
{
  char ans,Start[10],End[10];
  int wt,i,j;
  cout<<"Enter the number of vertices: ";
  cin>>no;
  cout<<"\nEnter the vertices: ";
  for(i=0;i<no;i++)
          cin>>vertices[i];
  do
  {
    cout<<"\nEnter Start and End vertex of the edge: ";
    cin>>Start>>End;
    cout<<"Enter weight: ";
    cin>>wt;
    i=Position(Start);
    j=Position(End);
    cost[i][j]=cost[j][i]=wt;
    cout<<"\nDo you want to add more edges (Y=YES/N=NO)? : ";	/* Type 'Y' or 'y' for YES and 'N' or 'n' for NO */
    cin>>ans;
  }while(ans=='y' || ans=='Y');
}

/* Displaying Cost matrix */
void Graph::display()
{
  int i,j;
  cout<<"\n\nCost matrix: ";
  for(i=0;i<no;i++)
  {
 		cout<<"\n";
 		for(j=0;j<no;j++)
   	cout<<"\t"<<cost[i][j];
  }
}

/* Retrieving position of vertices in 'vertices' array */
int Graph::Position(char key[10])
{
  int i;
  for(i=0;i<10;i++)
  if(strcmp(vertices[i],key)==0)
    return i;
return -1;		 
}

void Graph::kruskal_algo()
{
  int i,j,v[10]={0},x,y,Total_cost=0,min,gr=1,flag=0,temp,d;

  while(flag==0)
  {
    min=999;
 		for(i=0;i<no;i++)
    {  
      for(j=0;j<no;j++)
     		{
        if(cost[i][j]<min)
        		{
          min=cost[i][j];
          x=i;
          y=j;
        		}
     		}
   	}
   	
    if(v[x]==0 && v[y]==0)
    {
      v[x]=v[y]=gr;
      gr++;
    }
    else if(v[x]!=0 && v[y]==0)
      v[y]=v[x];
    else if(v[x]==0 && v[y]!=0)
      v[x]=v[y];
    else
    {
      if(v[x]!=v[y])
      {
        d=v[x];
        for(i=0;i<no;i++)
        {
          if(v[i]==d)
          v[i]=v[y];
        }//end for
      }
    }
    
    cost[x][y]=cost[y][x]=999;
    Total_cost=Total_cost+min;			/* calculating cost of minimum spanning tree */
    cout<<"\n\t"<<vertices[x]<<"\t\t"<<vertices[y]<<"\t\t"<<min;
  
   		temp=v[0]; flag=1;
   		for(i=0;i<no;i++)
   		{
     		if(temp!=v[i])
     		{
     		flag=0;
     		break;
     		}
   		}
  }
cout<<"\nTotal cost of the tree= "<<Total_cost;
}

int main()
{
  Graph g;
  g.creat_graph();
  g.display();

  cout<<"\n\n\nMinimum Spanning tree using kruskal algo=>";
  cout<<"\nSource vertex\tDestination vertex\tWeight\n";
  g.kruskal_algo();

return 0;
}

 

Input/Output:

Enter the number of vertices: 5
Enter the vertices: 0 1 2 3 4

Enter Start and End vertex of the edge: 0
1
Enter weight: 2

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 1
2
Enter weight: 3

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 1
4
Enter weight: 5

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 2
4
Enter weight: 7

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 0
3
Enter weight: 6

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 1
3
Enter weight: 8

Do you want to add more edges (Y=YES/N=NO)? : y

Enter Start and End vertex of the edge: 3
4
Enter weight: 9
Do you want to add more edges (Y=YES/N=NO)? : n

Cost matrix:
999     2     999      6     999
 2     999     3       8      5
999     3     999     999     7
 6      8     999     999     9 
999     5      7       9     999


Minimum Spanning tree using kruskal algo=>
Source vertex     Destination vertex     Weight
     0                    1                2
     1                    2                3
     1                    4                5
     0                    3                6
Total cost of the tree= 16

This is how we can implement Kruskal’s algorithm to find the minimum spanning tree in C++.

You may also read:

  1. How to create a CSV file in C++
  2. Find difference between two dates in C++


Leave a Reply

Your email address will not be published. Required fields are marked *