最小生成树C代码实例

在贪婪算法这一章提到了最小生成树的一些算法，首先是Kruskal算法，实现如下：

MST.h

#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(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;}