KRUSKAL's Algorithm Implementation Program

IMPLEMENTATION OF KRUSKALS ALGORITHM

PROGRAM:

#include
#include
#define INFINITY 999
typedef struct graph
{
int v1;
int v2,cost;
}GR;
GR g[20];
int tot_edges,tot_nodes;
void create();
void spanning_tree();
int minimum(int);
void main()
{
clrscr();
printf("\n Graph creation by adjacency matrix");
create();
spanning_tree();
getch();
}
void create()
{
int k;
printf("\n Enter the total no., of nodes");
scanf("%d",&tot_nodes);
printf("\n Enter the total no0., of edges");
scanf("%d",&tot_edges);
for(k=0;k{
printf("\n Enter the edges in(v1,v2) from");
scanf("%d%d",&g[k].v1,&g[k].v2);
printf("\n Enter the corresponding cost");
scanf("%d",&g[k].cost);
}
}
void spanning_tree()
{
int count,k,v1,v2,i,j,tree[10][10],pos,parent[10];
int sum;
int find(int i,int parent[]);
void union1(int i,int j,int parent[]);
count=0;
k=0;
sum=0;
for(i=0;iparent[i]=i;
while(count!=tot_nodes-1)
{
pos=minimum(tot_edges);
if(pos==-1)
break;
v1=g[pos].v1;
v2=g[pos].v2;
i=find(v1,parent);
j=find(v2,parent);
if(i!=j)
{
tree[k][0]=v1;
tree[k][1]=v2;
k++;
count++;
sum+=g[pos].cost;
union1(i,j,parent);
}
g[pos].cost=INFINITY;
}
if(count==tot_nodes-1)
{
printf("\n The Spanning tree is...,,");
printf("\n ..............\n ");
for(i=0;i{
printf("%d",tree[i][0]);
printf("_");
printf("%d",tree[i][0]);
printf("]");
}
printf("\n......");
printf("\n Cost of the spanning tree is=%d",sum);
}
else
{
printf("\n There is no spanning tree");
}
}
int minimum(int n)
{
int i,small,pos;
small=INFINITY;
pos=-1;
for(i=0;i{
if(g[i].cost{
small=g[i].cost;
pos=i;
}
}
return pos;
}
int find(int v2,int parent[])
{
while(parent[v2]!=v2)
{
v2=parent[v2];
}
return v2;
}
void union1(int i, int j, int parent[])
{
if(iparent[j]=i;
else
parent[i]=j;
}







OUTPUT:

Graph creation by adjacency matrix

Enter the total no of nodes 7

Enter the total no of edges 12

Enter the corresponding cost 1
Enter the edges in(v1,v2) from 1 2

Enter the corresponding cost 4
Enter the edges in(v1,v2) from 2 5

Enter the corresponding cost 7
Enter the edges in(v1,v2) from 5 7

Enter the corresponding cost 6
Enter the edges in(v1,v2) from 7 6

Enter the corresponding cost 5
Enter the edges in(v1,v2) from 6 3

Enter the corresponding cost 1
Enter the edges in(v1,v2) from 3 1

Enter the corresponding cost 2
Enter the edges in(v1,v2) from 1 4

Enter the corresponding cost 3
Enter the edges in(v1,v2) from 2 4

Enter the corresponding cost 6
Enter the edges in(v1,v2) from 7 4

Enter the corresponding cost 2
Enter the edges in(v1,v2) from 6 4

Enter the corresponding cost 4
Enter the edges in(v1,v2) from 3 4

The Spanning tree is...

[1_3][3_3][1_1][6_6][5_5][7_7]

Cost of the spanning tree is=15






CIET college Programs,LAB Programs for Engineering Students,DAA LAB Programs,DSA LAB Programs,Remoboys,karthik,Remokn,Student3k,programs source code,Design Analysis And Algorithms LAB Programs,Data Structures and Algorithms LAB Programs,LAB Codings,Coimbatore Institute of Engineering and Technology ( CIET )