Wij 当顶点i与顶点j之间有边时，且边上的权值为Wij时
A[i][j] =
? 当顶点i与顶点j之间无边时
<2> 图的表示
用n表示城市的个数，st表示起始城市，ed表示终点城市，dis表示两城市间的距离。下面
是构成该结构体的源代码：
typedef struct node { int st ;/*起点*/ int ed;/*终点*/ int dis ;/*距离*/ }node; node p[]； /*p[]数组用来储存城市和城市间的信息*/ 2 、算法的设计 <1> 克鲁斯卡尔算法设计
a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[ ]中。
b. 从p[ ]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加
入生成树；否则，加入到生成树中，计数器E累加1。
c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 d. 判断是否构成回路的方法：
设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中 或者两个顶点都不在S中，则不够成回路。
<2> 防止不能构成最小生成树的图
为避免输入的图构成的不是连通图，设计了judge ( ) 函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆算法，经过改编，形成了新的函数。
<3> 模块结构及功能
- 6 -
主程序
输入城市信息
判断是 初始化 否构成 回路
打印输出最
小生成树及
代价
a) int main ( ) //主程序 b) int menu ( ) //菜单函数
c) void create ( ) //输入城市信息函数 d) void judge ( ) //判断是否能够生成最小生成树函数 e) void display( ) //打印输出
f) void set ( ) //初始化pre[],rank[]函数 g) void find（ ） //判断是否构成回路函数
h) void Union ( ) //将能构成最小生成树的边添加到一个集合 i) void Krushal( ) //克鲁斯算法求最小生成树
将能够最小生成树的边集合 判断是否为连通图 求最小生成树 退出 <4> 主要模块算法描述
Krushal算法描述：
/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/*初始化*/ {
pre[x] = x; rank[x] = 0; }
int find(int x)/*找到这个点的祖先*/
- 7 -
{
if(x != pre[x])
pre[x] = find(pre[x]); return pre[x]; }
void Union(int x,int y)/*将这两个添加到一个集合里去*/ {
x = find(x); y = find(y);
if(rank[x] >= rank[y]) {
pre[y] = x; rank[x] ++; }
else pre[y] = x; }
void Kruskal( ) {
int ans = 0,i,j,k = 0; /*ans用来记录生成最小树的权总值*/ int index;
int count = 0; /*记录打印边的条数*/
for(i = 1;i <= n;i ++) /*初始化数组pre[x],rank[x]*/ set(i);
for(i = 1;i <= n;i ++) {
for(j = i + 1;j <= n;j ++) {
p[++k].st = i; p[k].ed = j;
p[k].dis = a[i][j]; /*先把所有城市之间的路段看成一个边*/ } }
for(i=1;i<=k;i++) /*把所有的边按从小到大进行排序*/ {
index=i;
for(j=i+1;j<=k;j++) if(p[j].dis for(i = 1;i <= k;i ++) { - 8 - if(find(p[i].st) != find(p[i].ed))/*如果这两点连接在一起不构成一个回路，则执行下面操作*/ { printf(\第%d条路段为：%d--%d,权值为%d\\n\,++ count,p[i].st,p[i].ed,p[i].dis);/*将这条边的起点、终点打印出来*/ ans += p[i].dis; /*说明这条路段要用*/ Union(p[i].st,p[i].ed); } } printf(\遍历所有城市得到最小生成树的代价为: %d\\n\\n\,ans); } 五、源程序清单（详见附录） 六、测试数据及测试结果 以一个6个城市、10条边的网络图为例进行测试 16 1 20 19 1 1 11 6 1 5 1 22 14 9 18 1 网络图 ?162019?16?11?6GE = ?5 2011?19???65 2214?18?9?922???1418?邻接矩阵 1、开始画面 - 9 - 2、输入信息 设置两顶点之间无边时∞权值为1000000 3、数据处理 (1)、判断能否构成最小生成树 （2）、遍历所有城市生成最小生成数 生成的最小生成树 - 10 - 1 4 16 3 18 11 2 5 6 6 5