/* Program for creating a minimum spanning tree from Kruskal's algorithm */
#include<stdio.h>
#define MAX 20

struct edge
{
	int u;
	int v;
	int weight;
	struct edge *link;
}*front = NULL;

int father[MAX]; /*Holds father of each node */
struct edge tree[MAX]; /* Will contain the edges of spanning tree */
int n;   /*Denotes total number of nodes in the graph */
int wt_tree=0; /*Weight of the spanning tree */
int count=0;    /* Denotes number of edges included in the tree */

/* Functions */
void make_tree();
void insert_tree(int i,int j,int wt);
void insert_pque(int i,int j,int wt);
struct edge *del_pque();

main()
{
	int i;

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

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

	printf("Enter number of nodes : ");
	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
			insert_pque(origin,destin,wt);
	}/*End of for*/
	if(i<n-1)
	{
		printf("Spanning tree is not possible\n");
		exit(1);
	}
}/*End of create_graph()*/

void make_tree()
{
	struct edge *tmp;
	int node1,node2,root_n1,root_n2;

	while( count < n-1) /*Loop till n-1 edges included in the tree*/
	{
		tmp=del_pque();
		node1=tmp->u;
		node2=tmp->v;

		printf("n1=%d  ",node1);
		printf("n2=%d  ",node2);

		while( node1 > 0)
		{
			root_n1=node1;
			node1=father[node1];
		}
		while( node2 >0 )
		{
			root_n2=node2;
			node2=father[node2];
		}
		printf("rootn1=%d  ",root_n1);
		printf("rootn2=%d\n",root_n2);

		if(root_n1!=root_n2)
		{
		      insert_tree(tmp->u,tmp->v,tmp->weight);
		      wt_tree=wt_tree+tmp->weight;
		      father[root_n2]=root_n1;
		}
	}/*End of while*/
}/*End of make_tree()*/

/*Inserting an edge in the tree */
void insert_tree(int i,int j,int wt)
{
	printf("This edge inserted in the spanning tree\n");
	count++;
	tree[count].u=i;
	tree[count].v=j;
	tree[count].weight=wt;
}/*End of insert_tree()*/

/*Inserting edges in the priority queue */
void insert_pque(int i,int j,int wt)
{
	struct edge *tmp,*q;

	tmp = (struct edge *)malloc(sizeof(struct edge));
	tmp->u=i;
	tmp->v=j;
	tmp->weight = wt;

	/*Queue is empty or edge to be added has weight less than first edge*/
	if( front == NULL || tmp->weight < front->weight )
	{
		tmp->link = front;
		front = tmp;
	}
	else
	{
		q = front;
		while( q->link != NULL && q->link->weight <= tmp->weight )
			q=q->link;
		tmp->link = q->link;
		q->link = tmp;
		if(q->link == NULL)	/*Edge to be added at the end*/
			tmp->link = NULL;
	}/*End of else*/
}/*End of insert_pque()*/

/*Deleting an edge from the priority queue*/
struct edge *del_pque()
{
	struct edge *tmp;
	tmp = front;
	printf("Edge processed is %d->%d  %d\n",tmp->u,tmp->v,tmp->weight);
	front = front->link;
	return tmp;
}/*End of del_pque()*/