Scribd
Upload
32 views2 pages

Krushkal Algorithm

The document presents a C implementation of Kruskal's algorithm for finding the minimum spanning tree of a graph. It prompts the user to input the number of vertices and a cost matrix, then calculates and displays the edges included in the minimum spanning tree along with the total minimum cost. The example output demonstrates the algorithm's functionality with a sample graph of three vertices.

Uploaded by

deadshotlev
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
32 views2 pages

Krushkal Algorithm

The document presents a C implementation of Kruskal's algorithm for finding the minimum spanning tree of a graph. It prompts the user to input the number of vertices and a cost matrix, then calculates and displays the edges included in the minimum spanning tree along with the total minimum cost. The example output demonstrates the algorithm's functionality with a sample graph of three vertices.

Uploaded by

deadshotlev
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

KRUSHKAL ALGORITHM

#include<stdio.h>
int ne=1,cost[10][10],min,a,b;
void main()
{
int i,j,n,u,v,parent[10],mincost=0;
printf("Enter the no of vertex:");
scanf("%d",&n);
for(i=1;i<=n;i++)
parent[i]=0;
printf("Enter the cost matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[u])
{
u=parent[u];
}
while(parent[v])
{
u=parent[v];
}
if(u!=v)
{
printf("Edge %d(%d to %d) min cost is %d\n",ne++,u,v,min);
mincost+=min;
cost[a][b]=cost[b][a]=999;
}
}
printf("The minimum cost= %d",mincost);
}

OUTPUT:

Enter the no of vertex:3


Enter the cost matrix:
0 4 3
4 0 2
3 2 0
Edge 1(2 to 3) min cost is 2
Edge 2(1 to 3) min cost is 3
The minimum cost= 5

You might also like