Kruskal’s algorithm in C++
By Pritam HandeIn 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.
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:
Hello,Sir
This code for Kruskal’s algorithm is not correct.
check this code for the data given below:
(source dest weight)
(0, 1, 4)
(0, 7, 8)
(1, 2, 8)
(1, 7, 11)
(2, 3, 7)
(2, 8, 2)
(2, 5, 4)
(3, 4, 9)
(3, 5, 14)
(4, 5, 10)
(5, 6, 2)
(6, 7, 1)
(6, 8, 6)
(7, 8, 7)
Your code is giving output 58, but it should be 37
Yeah. That’s right. I checked the code using the input below, and it doesn’t give the right answer.
2 1 4
3 2 7
4 5 6
1 3 8
1 4 10
5 2 8
5 6 4
1 5 5
4 2 5