Scribd
Upload
17 views2 pages

Kruskals Algorithm

The document contains a C program that implements Kruskal's algorithm to find the minimum spanning tree of a graph represented by an adjacency matrix. It defines necessary data structures and functions for sorting edges, finding connected components, and performing union operations. The program prompts the user for the number of vertices and the adjacency matrix, then outputs the edges of the minimum spanning tree and its total cost.

Uploaded by

bowycefi
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
17 views2 pages

Kruskals Algorithm

The document contains a C program that implements Kruskal's algorithm to find the minimum spanning tree of a graph represented by an adjacency matrix. It defines necessary data structures and functions for sorting edges, finding connected components, and performing union operations. The program prompts the user for the number of vertices and the adjacency matrix, then outputs the edges of the minimum spanning tree and its total cost.

Uploaded by

bowycefi
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>

#define MAX 30

typedef struct edge


{
int u,v,w;
}edge;

typedef struct edgelist


{
edge data[MAX];
int n;
}edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

void main()
{
int i,j,total_cost;
printf("\nEnter number of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
kruskal();
print();
}

void kruskal()
{
int belongs[MAX],i,j,cno1,cno2;
elist.n=0;

for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(G[i][j]!=0)
{
[Link][elist.n].u=i;
[Link][elist.n].v=j;
[Link][elist.n].w=G[i][j];
elist.n++;
}
}

sort();
for(i=0;i<n;i++)
belongs[i]=i;
spanlist.n=0;
for(i=0;i<elist.n;i++)
{
cno1=find(belongs,[Link][i].u);
cno2=find(belongs,[Link][i].v);
if(cno1!=cno2)
{
[Link][spanlist.n]=[Link][i];
spanlist.n=spanlist.n+1;
union1(belongs,cno1,cno2);
}
}
}

int find(int belongs[],int vertexno)


{
return(belongs[vertexno]);
}

void union1(int belongs[],int c1,int c2)


{
int i;
for(i=0;i<n;i++)
if(belongs[i]==c2)
belongs[i]=c1;
}

void sort()
{
int i,j;
edge temp;
for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if([Link][j].w>[Link][j+1].w)
{
temp=[Link][j];
[Link][j]=[Link][j+1];
[Link][j+1]=temp;
}
}

void print()
{
int i,cost=0;
for(i=0;i<spanlist.n;i++)
{
printf("\n%d\t%d\t%d",[Link][i].u,[Link][i].v,[Link][i].w);
cost=cost+[Link][i].w;
}

printf("\n\nCost of the spanning tree=%d",cost);


}

You might also like