Scribd
Upload
15 views2 pages

Kuskals

This document presents a C program that implements Kruskal's algorithm for finding the Minimum Cost Spanning Tree (MST) of a graph. It prompts the user to input the number of vertices and the cost adjacency matrix, then calculates and displays the edges of the MST along with the total minimum cost. The program uses union-find data structures to manage and unite the sets of vertices.

Uploaded by

upparasrividya971
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
15 views2 pages

Kuskals

This document presents a C program that implements Kruskal's algorithm for finding the Minimum Cost Spanning Tree (MST) of a graph. It prompts the user to input the number of vertices and the cost adjacency matrix, then calculates and displays the edges of the MST along with the total minimum cost. The program uses union-find data structures to manage and unite the sets of vertices.

Uploaded by

upparasrividya971
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

#include<stdio.

h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[10][10],parent[10];
int find(int);
int uni(int,int);
int main()
{
printf("\n\tImplementation of Kruskal's algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency 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;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
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;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d to %d cost=%d\n",a,b,min);
mincost +=min;
ne++;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}

You might also like