Krushkal's Algorithm - 1 and 2

Krushkal's Algorithm - 2

/* C Program on Krushkal's Algorithm */

#include< stdio.h>

#include< stdlib.h>

void main()

{

int graph[15][15],s[15],pathestimate[15],mark[15];

int num_of_vertices,source,i,j,u,predecessor[15];

int count=0;

int minimum(int a[],int m[],int k);

void printpath(int,int,int[]);

printf("\nEnter The No. Of Vertices\n");

m scanf("%d",&num_of_vertices);

if(num_of_vertices< =0)

{

printf("\nThis Is Meaningless\n");

exit(1);

}

printf("\nEnter The Adjacent Matrix\n");

for(i=1;i< =num_of_vertices;i++)

{

printf("\nEnter The Elements Of Row %d\n",i);

for(j=1;j< =num_of_vertices;j++)

scanf("%d",&graph[i][j]);

}

printf("\nEnter The Source Vertex\n");

scanf("%d",&source);

for(j=1;j< =num_of_vertices;j++)

{

mark[j] = 0;

pathestimate[j] = 999;

predecessor[j] = 0;

}

pathestimate[source]=0;

while(count< num_of_vertices)

{

u = minimum(pathestimate,mark,num_of_vertices);

s[++count] = u;

mark[u] = 1;

for(i=1;i< =num_of_vertices;i++)

{

if(graph[u][i]>0)

{

if(mark[i]!=1)

{

if(pathestimate[i]>pathestimate[u]+graph[u][i])

{

pathestimate[i] = pathestimate[u]+graph[u][i];

predecessor[i] = u;

}

}

}

}

}

for(i=1;i< =num_of_vertices;i++)

{

printpath(source,i,predecessor);

if(pathestimate[i]!=999)

printf("->(%d)\n",pathestimate[i]);

}

}

int minimum(int a[],int m[],int k)

{

int mi=999;

int i,t;

for(i=1;i< =k;i++)

{

if(m[i]!=1)

{

if(mi>=a[i])

{

mi = a[i];

t = i;

}

}

}

return t;

}

void printpath(int x,int i,int p[])

{

printf("\n");

if(i==x)

printf("%d",x);

else if(p[i]==0)

printf("Number Path From %d To %d",x,i);

else

{

printpath(x,p[i],p);

printf("..%d",i);

}

}

/****************

Enter The No. Of Vertices

6

Enter The Adjacent Matrix

Enter The Elements Of Row 1

0 1 1 1 0 0

Enter The Elements Of Row 2

0 0 1 0 1 0

Enter The Elements Of Row 3

0 0 0 1 1 1

Enter The Elements Of Row 4

0 0 0 0 0 1

Enter The Elements Of Row 5

0 0 0 0 0 1

Enter The Elements Of Row 6

0 0 0 0 0 0

Enter The Source Vertex

1

1->(0)

1..2->(1)

1..3->(1)

1..4->(1)

1..3..5->(2)

1..4..6->(2)

*/

Krushkal's Algorithm

/* C Program On Krushkal's Algorithm */

#include < stdio.h>

#include < conio.h>

typedef struct

{

int node1;

int node2;

int wt;

}edge;

void sortedges(edge a[],int n)

{

int i,j;

edge temp;

for(i=0;i< n-1;++i)

for(j=i+1;j< n;++j)

if(a[i].wt>a[j].wt){temp=a[i];a[i]=a[j];a[j]=temp;}

}

int checkcycle(int p[],int i,int j)

{

int v1,v2;

v1 = i;

v2 = j;

while(p[i]>-1)

i = p[i];

while(p[j]>-1)

j = p[j];

if(i!=j)

{

p[j]=i;

printf("%d %d\n",v1,v2);

return 1;

}

return 0;

}

void main()

{

edge e[100];

int parent[100];

int n,i,j,m,k = 1,cost = 0;

clrscr();

printf("KRUSKAL's ALGORITHM\n");

printf("Enter number of nodes\n");

scanf("%d",&n);

for(i=0;i< n;++i)

parent[i]=-1;

i = 0;

printf("Enter number of edges\n");

scanf("%d",&m);

for(i=0;i< m;++i)

{

printf("enter an edge and wt\n");

scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);

}

sortedges(e,m);

printf("\n\nEdges of the tree\n");

i = 0;

while(k< n)

{

if(checkcycle(parent,e[i].node1,e[i].node2))

{

k++;

cost=cost+e[i].wt;

i++;

}

}

printf("cost = %d",cost);

getch();

}

--
http://www.venkatmails.blogspot.com/

Venkat Mails, Fun , Cool pictures, Fun messages, Sardar Jokes, Quotations Moral stories Fun stories

http://www.venkatmails.blogspot.com/