#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 <stdlib.h> #include <stdio.h> 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(NODE n) {  n->parent = n; } int find(NODE n, NODE ds) {  if (n->parent == n)  {   ds->data = n->data;   ds->flag = 1;   ds->parent = n->parent;  }  if (n->parent != n)   find(n->parent, ds); } int merge(NODE da, NODE db) {  if (da->flag)   db->parent = da;  else   da->parent = db; } int comp(const void *ea, const void *eb) {  if ((*(edge **)ea)->w > (*(edge **)eb)->w) return 1;  else if ((*(edge **)ea)->w == (*(edge **)eb)->w ) return 0;  else return -1; }