# 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. ## Program to implement Kruskal’s algorithm in C++ ( Minimum Spanning Tree )

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

class Graph
{
char vertices;
int cost,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,End;
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)
{
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={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; 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++.