15-11-2012, 04:34 PM
Prim's algorithms
Prim's algorithms.docx (Size: 14.76 KB / Downloads: 18)
Coding:
#include<stdio.h>
#include<conio.h>
#define max 10
#define infinity 9999
struct node
{
int predecessor;
int dist,status;
};
struct edge
{
int u;int v;
};
int adj[max][max];
int n;
void main()
{
int i,j;
int path[max];
int mincost,count;
struct edge tree[max];
clrscr();
create_graph();
count=maketree(tree,&mincost);
printf("\nEdges to be included in spanning tree are:\n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
printf("\nweight of spanning tree is:%d\n",mincost);
}
create_graph()
{
int i,max_edges,source,destin,wt;
printf("Enter no. of vertices:");
scanf("%d",&n);
max_edges=n*(n-1)/2;
for(i=1;i<max_edges;i++)
{
printf("Enter edge %d(00 to quit):",i);
scanf("%d%d",&source,&destin);
if((source==0)&&(destin==0))
break;
printf("Enter wt for this edge:");
scanf("%d",&wt);
if(source>n|destin>n|source<=0|destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
{
adj[source][destin]=wt;
adj[destin][source]=wt;
}
}
if(i<n-1)
{
printf("spanning tree is not possible\n");
exit(1);
}
return;
}
int maketree(struct edge tree[max],int *weight)
{
struct node state[max];
int i,k,min,count,current,newdist;int m;
int u1,v1;
*weight=0;
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist=infinity;
state[i].status=0;
}
state[1].predecessor=0;
state[1].dist=0;
state[1].status=1;
current=1;
count=0;
while(all_perm(state)!=1)
{
for(i=1;i<=n;i++)
{
if(adj[current][i]>0&&state[i].status==0)
{
if(adj[current][i]<state[i].dist)
{
state[i].predecessor=current;
state[i].dist=adj[current][i];
}
}
}
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status==0&&state[i].dist<min)
{
min=state[i].dist;
current=i;