IMPLEMENTATION OF PRIMS ALGORITHM

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

void distance(int destination);

int n;

int load[100][100];

char mst[100];

int m[100];

int whoto[100];

void distance(int destination)

{

int i;

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

if((load[destination][i]!=0)&&(m[i]>load[destination][i]))

{

m[i]=load[destination][i];

whoto[i]=destination;

}}

void main()

{

int i,j,total,minspan;

clrscr();

printf("enter the number of nodes:");

scanf("%d",&n);

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

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

{

printf("enter the weight from %d to %d",i,j);

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

}

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

m[i]=10000;

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

mst[i]=0;

printf("adding node %c\n",0+'a');

mst[0]=1;

distance(0);

total=0;

for(minspan=1;minspan<n;++minspan)

{

int min=-1;

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

if(!mst[i])

if((min==-1)||(m[min]>m[i]))

min=i;

printf("adding edges %c---%c\n",whoto[min]+'a',min+'a');

mst[min]=1;

total+=m[min];

distance(min);

}

printf("total distance:%d\n",total);

getch();

}

OUTPUT:

          enter the number of nodes:3

enter the weight from 0 to 0 5

enter the weight from 0 to 1 4

enter the weight from 0 to 2 3

enter the weight from 1 to 0 3

enter the weight from 1 to 1 7

enter the weight from 1 to 2 4

enter the weight from 2 to 0 1

enter the weight from 2 to 1 2

enter the weight from 2 to 2 4

adding node a

adding edges a---c

adding edges c---b

total distance:5

IMPLEMENTATION OF KRUSKAL’S ALGORITHM      

#include<stdio.h>

#define INFINITY 999

typedef struct graph

{

int v1;

int v2;

int cost;

}graph;

graph c[20];

int min(int);

int find(int v2,int p[]);

void combine(int i,int j,int p[]);

void main()

{

int t[10][10],v1,v2,cost,low,i,k,j,n,m;

int p[20],count=0,sum=0;

clrscr();

printf("\nenter the no of vertices:");

scanf("%d",&n);

printf("\n enter the no of edges:");

scanf("%d",&m);

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

{

printf("\nthe cost of the edge from");

scanf("%d",&c[k].v1);

printf("\t\t to ");

scanf("%d",&c[k].v2);

printf(" and the cost is");

scanf("%d",&c[k].cost);

}

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

p[i]=i;

k=0;

while(count!=(n-1))

{

low=min(m);

if(low==-1)

break;

v1=c[low].v1;

v2=c[low].v2;

i=find(v1,p);

j=find(v2,p);

if(i!=j)

{

t[k][0]=v1;

t[k][1]=v2;

k++;

count++;

sum=sum+c[low].cost;

combine(i,j,p);

}

c[low].cost=INFINITY;

}

printf("\nminimum spanning tree is:");

if(count==(n-1))

{

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

printf("\t%d->%d",t[i][0],t[i][1]);

printf("\n\nthe cost of the spanning tree is %d",sum);

}

getch();

}

int min(int n)

{int i,s,min;

s=INFINITY;

min=-1;

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

if(c[i].cost<s)

{

s=c[i].cost;

min=i;

}

return min;

}

int find(int v2,int p[])

{while(p[v2]!=v2)

{

v2=p[v2];

}

return v2;

}

void combine(int i,int j,int p[])

{if(i<j)

p[j]=i;

else

p[i]=j;

}

OUTPUT:

enter the no of vertices:6

enter the no of edges:9

the cost of the edge from 1 to 2

 the cost is5

the cost of the edge from 2 to 3

 the cost is5

the cost of the edge from 1 to 4

  the cost is3

the cost of the edge from  2 to 4

the cost is2

the cost of the edge from 2 to 5

the cost is6

the cost of the edge from 4 to 5

the cost is1

the cost of the edge from 3 to 5

the cost is1

the cost of the edge from 5  to 6

the cost is2

the cost of the edge from 3  to 6

 the cost is4

minimum spanning tree is:       4->5    3->5    2->4    5->6    1->4

the cost of the spanning tree is 9