用 Kruskal 算法求解最小生成树问题：Kruskal 算法采用了最短边策略
(设 G=(V,E)是一个无向连通网，令 T=(U，TE)是 G 的最小生成树。最短边策略从
TE={}开始，每一次贪心选择都是在边集 E 中选择最短边(u,v)，如果边(u,v)加入集
合 TE 中不产生回路，则将边(u,v)加入边集 TE 中，并将它在集合 E 中删去。)，它
使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两
棵树合并，最后合并成一棵树。
Kruskal 算法实现代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5
#define MAX_VERTEX_NUM 20
typedef char Vertex[MAX_NAME];/*顶点名字串*/
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/
struct MGraph/*定义图*/
{
6Vertex vexs[MAX_VERTEX_NUM];
6AdjMatrix arcs;
6int vexnum,arcnum;
}
typedef struct
{
6 Vertex adjvex; /*当前点*/
6 int lowcost;666 /*代价*/
}minside[MAX_VERTEX_NUM];
int LocateVex(MGraph G,Vertex u)//定位
{
6 int i;
6 for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;
6 return -1;
}
void CreateGraph(MGraph &G)
{
6 int i,j,k,w;
6 Vertex va,vb;
6 printf("请输入无向网 G 的顶点数和边数(以空格为分隔)");
6 scanf("%d %d",&G.vexnum,&G.arcnum);
6 printf("请输入%d 个顶点的值(<%d 个字符):",G.vexnum,MAX_NAME);
6 for(i=0;i<G.vexnum;++i) /* 构造顶点集*/
666 scanf("%s",G.vexs[i]);
6 for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/
评论7