（3）、退出
七、课程设计总结
通过最小生成树的学习，我学会了树的多种存储结构和遍历方法，最小生成树的设计可以应用于我们生活中。我们可以把生活中遇到的实际问题转化为一种算法问题来进行解决。
八、附录
源程序：
#include
typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/ {
int st; /*起点*/ int ed; /*终点*/ int dis;/*距离*/ }node;
node p[1000],temp; /*p记录城市信息*/
int pre[1000],rank[1000];/*用于判断是否构成回路*/
int n=0,a[100][100];/*n表示城市个数，a[][]记录城市间权值*/
int menu( ) /*菜单函数*/ { int m;
printf(\求最小生成树\\n\);
printf(\); printf(\输入城市之间的信息\\n\);
printf(\判断是否能构成一个最小生成树\\n\); printf(\遍历所有城市生成最小生成树\\n\); printf(\退出\\n\);
printf(\); printf(\请输入所选功能--4\\n\); scanf(\,&m);
- 11 -
return m; }
/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/*初始化*/ {
pre[x] = x; }
int find(int x)/*找到这个点的祖先*/ {
if(x != pre[x])
pre[x] = find(pre[x]); return pre[x]; }
void Union(int x,int y)/*将这两个添加到一个集合里去*/ {
x = find(x); y = find(y); 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 - 12 - p[index]=p[i]; p[i]=temp; } for(i = 1;i <= k;i ++) { 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); } void create( ) /*输入城市信息*/ { int i,j; if(n != 0) { char str[100]; printf(\是否要确定输入新的城市之间的信息? (y/n) ?\\n\); scanf(\,str); if(strcmp(str,\) == 0 ) return ; } printf(\请输入城市的个数:\\n\); scanf(\,&n); printf(\输入%d个城市的邻接矩阵:\\n\,n); for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) scanf(\,&a[i][j]); } } void display( ) /*显示生成的最小生成树*/ { if(n == 0) { printf(\这里没有城市之间的信息\\n\); return; } - 13 - printf(\遍历所有城市得到最小生成树为：\\n\\n\\n\); Kruskal( ); } void judge( )/*判断是否能够生成最小生成树*/ { int close[100],low[100],i,j,ans = 0;/*close[j]表示离j最近的顶点，low[j]表示离j最短的距离*/ int use[100]; use[1] = 1; for(i = 2;i <= n;i ++) { low[i] = a[1][i]; /*初始化*/ close[i] = 1; use[i] = 0; } for(i = 1;i < n;i ++) { int min = 1000000,k = 0; for(j = 2;j <= n;j ++) { if(use[j] == 0 && min > low[j])/*找到最小的low[]值，并记录*/ { min = low[j]; k = j; } } for(j = 2;j <= n;j ++) { if(use[j] == 0 && low[j] > a[k][j]) { low[j] = a[k][j]; /*修改low[]值和close[]值*/ close[j] = k; } } if(a[close[k]][k]>=1000000) { count=1; } } if(count==1) printf(\不能构成最小生成树\\n\ else printf(\能构成最小生成树\\n\ - 14 - } int main( ) /*主函数*/ { while(1) { switch( menu( ) ) { case 1:create( );break;/*输入城市信息*/ case 2:judge( );break;/*判断是否能够生成最小生成树*/ case 3:display( );break; /*显示生成的最小生成树*/ case 4:exit( 0 ); } } return 0; } 参考书目 [1] [2] [3] 数据结构 严蔚敏，吴伟民 清华大学出版社 数据结构——习题与解析 严蔚敏，吴伟民 清华大学出版社 Data Structures and Algorithm Analysis in C: Second Edition, Mark Allen Weiss, Person [4] C语言课程设计案例精编，郭翠英，中国水利出版社 - 15 -