prims.c

Graph Programs in C

/* Program for creating minimum spanning tree from Prim's algorithm */
#include<stdio.h>

#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999

struct node
{
	int predecessor;
	int dist; /*Distance from predecessor */
	int status;
};

struct edge
{
	int u;
	int v;
};

int adj[MAX][MAX];
int n;

main()
{
	int i,j;
	int path[MAX];
	int wt_tree,count;
	struct edge tree[MAX];

	create_graph();
	printf("Adjacency matrix is :\n");
	display();

	count = maketree(tree,&wt_tree);

	printf("Weight of spanning tree is : %d\n", wt_tree);
	printf("Edges 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);
	}
}/*End of main()*/

create_graph()
{
	int i,max_edges,origin,destin,wt;

	printf("Enter number of vertices : ");
	scanf("%d",&n);
	max_edges=n*(n-1)/2;

	for(i=1;i<=max_edges;i++)
	{
		printf("Enter edge %d(0 0 to quit) : ",i);
		scanf("%d %d",&origin,&destin);
		if((origin==0) && (destin==0))
			break;
		printf("Enter weight for this edge : ");
		scanf("%d",&wt);
		if( origin > n || destin > n || origin<=0 || destin<=0)
		{
			printf("Invalid edge!\n");
			i--;
		}
		else
		{
			adj[origin][destin]=wt;
			adj[destin][origin]=wt;
		}
	}/*End of for*/
	if(i<n-1)
	{
		printf("Spanning tree is not possible\n");
		exit(1);
	}
}/*End of create_graph()*/

display()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%3d",adj[i][j]);
		printf("\n");
	}
}/*End of display()*/

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;
	/*Make all nodes temporary*/
	for(i=1;i<=n;i++)
	{
		state[i].predecessor=0;
		state[i].dist = infinity;
		state[i].status = TEMP;
	}
	/*Make first node permanent*/
	state[1].predecessor=0;
	state[1].dist = 0;
	state[1].status = PERM;

	/*Start from first node*/
	current=1;
	count=0; /*count represents number of nodes in tree */
	while( all_perm(state) != TRUE ) /*Loop till all the nodes become PERM*/
	{
		for(i=1;i<=n;i++)
		{
			if ( adj[current][i] > 0 && state[i].status == TEMP )
			{
				if(  adj[current][i] < state[i].dist )
				{
					state[i].predecessor = current;
					state[i].dist = adj[current][i];
				}
			}
		}/*End of for*/

		/*Search for temporary node with minimum distance
		and  make it current node*/
		min=infinity;
		for(i=1;i<=n;i++)
		{
			if(state[i].status == TEMP && state[i].dist < min)
			{
				min = state[i].dist;
				current=i;
			}
		}/*End of for*/

		state[current].status=PERM;

		/*Insert this edge(u1,v1) into the tree */
		u1=state[current].predecessor;
		v1=current;
		count++;
		tree[count].u=u1;
		tree[count].v=v1;
		/*Add wt on this edge to weight of tree	*/
		*weight=*weight+adj[u1][v1];
	}/*End of while*/
	return (count);
}/*End of maketree()*/

/*This function returns TRUE if all nodes are permanent*/
int all_perm(struct node state[MAX] )
{
	int i;
	for(i=1;i<=n;i++)
	   if( state[i].status == TEMP )
	       return FALSE;
	return TRUE;
}/*End of all_perm()*/