Senin, 22 September 2014

IMPLEMENTATION OF KRUSKALS ALGORITHM

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;i
parent[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(i
parent[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 )


0 komentar:

Posting Komentar

Blog Archive