#ifndef H_MST
#define H_MST

#define NODE node *
#define G graph *
#define MST edge **

/* the undirect graph start */
typedef struct _node {
	char data;
	int flag;
	struct _node *parent;
} node;

typedef struct _edge {
	node *A;
	node *B;
	int w;
} edge;

typedef struct _graph {
	node **nodelist;
	int nodeLen;
	edge **edgelist;
	int edgeLen;
} graph;

/* the undirect graph end */

int kruskal(G , edge *[]);

int makeset(NODE);

int find(NODE , NODE);

int merge(NODE , NODE);

int comp(const void *, const void *);

#endif

#include "mst.h"
#include 
  
   
#include 
   
     int main(int argc, char *argv[]) { /* Construct the undirect connected graph */ graph g; g.nodeLen = 6; g.edgeLen = 10; node node_a, node_b, node_c, node_d, node_e, node_f; edge edge_1, edge_2, edge_3, edge_4, edge_5, edge_6, edge_7, edge_8, edge_9, edge_10; node_a.data = 'a'; node_a.flag = 0; node_a.parent = (node *)malloc(sizeof(node)); node_b.data = 'b'; node_b.flag = 0; node_b.parent = (node *)malloc(sizeof(node)); node_c.data = 'c'; node_c.flag = 0; node_c.parent = (node *)malloc(sizeof(node)); node_d.data = 'd'; node_d.flag = 0; node_d.parent = (node *)malloc(sizeof(node)); node_e.data = 'e'; node_e.flag = 0; node_e.parent = (node *)malloc(sizeof(node)); node_f.data = 'f'; node_f.flag = 0; node_f.parent = (node *)malloc(sizeof(node)); edge_1.A = &node_a; edge_1.B = &node_b; edge_1.w = 5; edge_2.A = &node_a; edge_2.B = &node_c; edge_2.w = 6; edge_3.A = &node_a; edge_3.B = &node_d; edge_3.w = 4; edge_4.A = &node_b; edge_4.B = &node_c; edge_4.w = 1; edge_5.A = &node_b; edge_5.B = &node_d; edge_5.w = 2; edge_6.A = &node_c; edge_6.B = &node_d; edge_6.w = 2; edge_7.A = &node_c; edge_7.B = &node_e; edge_7.w = 5; edge_8.A = &node_c; edge_8.B = &node_f; edge_8.w = 3; edge_9.A = &node_d; edge_9.B = &node_f; edge_9.w = 4; edge_10.A = &node_e; edge_10.B = &node_f; edge_10.w = 4; node **nodelist; nodelist = (node **)malloc(sizeof(node *) * g.nodeLen); edge **edgelist; edgelist = (edge **)malloc(sizeof(edge *) * g.edgeLen); nodelist[0] = &node_a; nodelist[1] = &node_b; nodelist[2] = &node_c; nodelist[3] = &node_d; nodelist[4] = &node_e; nodelist[5] = &node_f; edgelist[0] = &edge_1; edgelist[1] = &edge_2; edgelist[2] = &edge_3; edgelist[3] = &edge_4; edgelist[4] = &edge_5; edgelist[5] = &edge_6; edgelist[6] = &edge_7; edgelist[7] = &edge_8; edgelist[8] = &edge_9; edgelist[9] = &edge_10; g.nodelist = nodelist; g.edgelist = edgelist; edge *X[g.nodeLen-1]; int e = 0; while (e < g.edgeLen) { printf("%c-%c %d\n", g.edgelist[e]->A->data, g.edgelist[e]->B->data, g.edgelist[e]->w); e++; } printf("------------------------------------------------------\n"); kruskal(&g, X); e = 0; while (e < (g.nodeLen-1)) { printf("%c-%c %d\n", X[e]->A->data, X[e]->B->data, X[e]->w); e++; } } int kruskal(G g, edge *pX[]) { int i, j; /* Initially every disjoint set have one node */ for (i = 0; i < g->nodeLen; i++) makeset(g->nodelist[i]); /* sort the edgelist */ qsort(g->edgelist, g->edgeLen, sizeof(edge *), comp); int e = 0; while (e < g->edgeLen) { printf("%c-%c %d\n", g->edgelist[e]->A->data, g->edgelist[e]->B->data, g->edgelist[e]->w); e++; } printf("------------------------------------------------------\n"); node da, db; da.parent = (node *)malloc(sizeof(node)); db.parent = (node *)malloc(sizeof(node)); for (j = 0; j < g->edgeLen; j++) { find(g->edgelist[j]->A, &da); find(g->edgelist[j]->B, &db); if (da.data != db.data) { merge(g->edgelist[j]->A, g->edgelist[j]->B); *pX++ = g->edgelist[j]; } } } int makeset