【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include ＜stdio. h＞ #include ＜stdlib. h＞ #define MAXN 30 typedef struct { int v1,v2; /*一条边依附的两个顶点*/ int weight; /*边上的权值*/ }EDGE; typedef struct { int Vnum; /*图中的顶点数目*/ EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/ }Graph; typedef struct node{ /*用链表存储同一个连通分量的顶点*/ int v; struct node *next; }Alist; void heapadjust(EDGE data[], int s, int m) { /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/ int j; EDGE t; t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/ for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/ if(j＜m && (1) ) ++j; if(!(t. weight＞data[j]. weight)) break; data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/ }/*for*/ data[s]=t; /*将备份元素插入由s所指出的插入位置*/ }/*heapadjust*/ int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/ { int k=0; /*记录图中边的数目*/ int n; int v1,v2; int w; printf("vertex number of the graph:"); scanf("%d", &n); /*输入图中的顶点数目*/ if(n＜1) return 0; p-＞Vnum=n; do{ printf("edge(vertex1,vertex2,weight):"); scanf("%d %d %d", &V1, &v2, &w); if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){ p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w; k++; }/*if*/ }while(!( (2) )); return k; /*返回图中边的数目*/ }/*creat_graph*/ int kruskal(Graph G, int enumber, int tree[][3]) { /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */ /*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/ int i, k, m, c=0; int v1, v2; Alist *p, *q, *a[MAXN]; for(i=0; i＜G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/ a[i]=(Alist*)malloc(sizeof(Alist)); if(!a[i]) { printf("\n mernory allocation error!"); exit(0); }/*if*/ a[i]-＞v=i; a[i]-＞next=NULL; }/*for*/ for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/ heapadjust( (3) ); k=G. Vnum; /*k用于计算图中的连通分量数目*/ m=enumber-1; i=0; do{ v1=G. e[0]. v1; v2=G. e[0]. v2; p=a[v1]; while(p && p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/ q=p; p=p-＞next; } if(!p){ /*当前边的顶点不在一个连通分量中*/ p=q; p-＞next=a[G. e[0]. v2]; p=a[G. e[0]. v1); /*加入边(v1,v2), 将两个连通分量合并为一个*/ while(p){a[p-＞v]= (4) ; p=p-＞next; } k--; /*连通分量数目减少一个*/ tree[i][0]=v1; /*记录加入最小生成树的边*/ tree[i][1]=v2; tree[i][2]=G. e[0]. weight; c+=G. e[0]. weight; ++i; }/*if*/ G. e[0]=G. e[m]; m--; heapadjust ( (5) ); } while(k＞1); /*当所有顶点不在同一个连通时, 继续*/ return c; /*返回最小生成树的代价*/ } /*kruskal*/ void main(void) { int i, enumber; int tree[MAXN][3]; int cost=0; Graph G; enumber=creat_graph(&G); cost=-kruskal(G,enumber,tree); printf("Minimum-Cost spanning tree(kruskal)：\n"); printf("edge\t weight\t\n"); for(i=0; i＜G. Vnum-1; ++i) printf("v %d –v %d \t %d\n", tree[i][0], tree[i][1], tree[i][2]); printf("Cost：%d\n", cost); }