广工数据结构课程设计最小生成树.doc

课程设计

课程名称 数据结构
学 院
专业班级
学 号
学生姓名
指导教师

2015年7月2日

1. 需求分析
题目：最小生成树问题
若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。
要求：
（1）利用克鲁斯卡尔算法求网的最小生成树。
（2）实现并查集。以此表示构造生成树过程中的连通分量。
（3） 以文本形式输出生成树中各条边以及他们的权值。
输入的形式和输入值的范围：十进制数，0—100。
输出的形式：十进制数。
程序所能达到的功能：遍历所有城市生成最小生成树。
测试数据：
正确数据：
城市个数3；3个城市的邻接矩阵：(1,2,3;2,100,4;3,4,6)
输出结果：第1条路段为1——2，权值为2
第2条路段为1——3，权值为3
遍历所有城市得到最小生成树的代价为：5
错误数据：城市个数3；城市的邻接矩阵：(-2,5,1;3,0,1;3,2,1)
输出结果：输入错误，请重新输入

2.概要设计
数据类型定义如下：
typedef struct node
{
int str; /*起点*/
int end; /*终点*/
int dis;/*距离*/
}node;
node p[max],temp; /*p记录城市信息*/
int pre[100],rank[100];/*用于判断是否构成回路*/
int n=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/
主程序流程如下：
3.详细设计
（1）克鲁斯卡尔算法思想基本描述：
假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n 顶点而无边的非连通图T=(V,{ })，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。
（2）克鲁斯卡尔算法设计：
a.  设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[ ]中。
b. 从p[ ]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。
c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 。
判断是否回路：
设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中   或者两个顶点都不在S中，则不够成回路。

/*需要的函数声明*/
int   main (  )             //主程序
int   menu (  )            //菜单函数
void  create (  )           //输入城市信息函数
void  judge (  )            //判断是否能够生成最小生成树函数
void  display(  )          //打印输出
void  set (  )            //初始化pre[],rank[]函数
void  find  (  )         //判断是否构成回路函数
void  Union (  )        //将能构成最小生成树的边添加到一个集合
void  Krushal(  )       //克鲁斯算法求最小生成树
/*菜单函数*/
int menu( )
{
int m;
printf("..........................2015年7月2日......................\n\n");
printf(" 求最小生成树\n");
printf(" ________________________________\n\n");
printf(" 1 输入城市之间的信息\n");
printf(" 2 判断是否能构成一个最小生成树\n");
printf(" 3 遍历所有城市生成最小生成树\n");
printf(" 0 退出\n");
printf(" ________________________________\n\n");
printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
if(m<0||m>3) return 4;
return m;
}
/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/
void set(int x)/*初始化*/
{
pre[x] = x;
rank[x] = 0;
}
/*找到这个点的祖先*/
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);
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].str = i;
p[k].end = j;
p[k].dis = arcs[i][j]; /*先把所有城市之间的路段看成一个边*/
}
}
for(i=1;i<=k;i++) /*把所有的边按从小到大进行排序*/
{
index=i;
for(j=i+1;j<=k;j++) if(p[j].dis <p[index].dis) index=j;
temp=p[index];
p[index]=p[i];
p[i]=temp;
}
for(i = 1;i <= k;i ++)
{
if(find(p[i].str) != find(p[i].end))/*如果这两点连接在一起不构成一个回路，则执行下面操作*/
{
printf("\t第%d条路段为：%d--%d,权值为%d\n",++ count,p[i].str,p[i].end,p[i].dis);/*将这条边的起点、终点打印出来*/
ans += p[i].dis; /*说明这条路段要用*/
Union(p[i].str,p[i].end);
}
}
printf("\t遍历所有城市得到最小生成树的代价为: %d\n\n",ans);
}
/*输入城市信息*/
void create( )
{
int i,j;
printf("请输入城市的个数（1—30）:\n");
scanf("%d",&n);
if(n<=0||n>30) {printf("输入错误，请重新输入\n");return ; }
printf("输入%d个城市存储边(带权)的数组（数值范围：1-99，∞用100表示，）:\n",n);
for(i = 1;i <= n;i ++)
{
for(j = 1;j <= n;j ++)
{
scanf("%d",&arcs[i][j]);
if(arcs[i][j]<1||arcs[i][j]>100)
{
printf("输入错误，请重新输入\n");
return ;
}
}
}
for(i=0;i<n;i++)
for(j=0;j<i;j++)
if(arcs[i][j]!=arcs[j][i]) /*判断矩阵是否对称*/
{
printf("输入错误，请重新输入\n");
return ;
}
}
/*显示生成的最小生成树*/
void display( ) {
if(n == 0)
{
printf("这里没有城市之间的信息\n");
return;
}
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] = arcs[1][i]; /*初始化*/
close[i] = 1;
use[i] = 0;
}
for(i = 1;i < n;i ++)
{
int min = 100000000,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] > arcs[k][j])
{
low[j] = arcs[k][j]; /*修改low[]值和close[]值*/
close[j] = k;
}
}
ans += arcs[close[k]][k];
}
if(ans >= 100000000) printf("不能构成最小生成树\n");
else printf("能构成最小生成树\n");
}
/*主函数*/
void main()
{
while(1)
{
switch( menu( ) )
{
case 1:create( );break;/*输入城市信息*/
case 2:judge( );break;/*判断是否能够生成最小生成树*/
case 3:display( );break; /*显示生成的最小生成树*/
case 0:exit( );
default:
printf("输入错误，请重新选择。\n");
break;
}
}
}
4.调试分析
本课程设计重点在于生成最小生成树算法。克鲁斯卡尔算法将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去，依次选够(n-1)条边,即得最小生成树。在克鲁斯卡尔算法中，图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的，该方法对于边相对比较多的不是很实用。
本课程设计为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用a[ i][ j]数组，利用邻接矩阵方式来储存城市与城市间信息 。
5.用户使用说明
按顺序依次输入城市之间的信息，判断是否能构成一个最小生成树，再生成遍历所有城市的最小生成树。如果输入过程中出现错误，需重新输入。城市存储边(带权)矩阵中的∞用100表示，矩阵必须对称。
6.测试结果

7. 源代码
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#define max 100
#define MAX_LNT 30

typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以
看成一个边*/
{
int str; /*起点*/
int end; /*终点*/
int dis;/*距离*/
}node;

node p[max],temp; /*p记录城市信息*/
int pre[100],rank[100];/*用于判断是否构成回路*/
int n=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/
int menu( ) /*菜单函数*/
{
int m;
printf("..........................2015年7月2日......................\n\n");
printf(" 求最小生成树\n");
printf(" ________________________________\n\n");
printf(" 1 输入城市之间的信息\n");
printf(" 2 判断是否能构成一个最小生成树\n");
printf(" 3 遍历所有城市生成最小生成树\n");
printf(" 0 退出\n");
printf(" ________________________________\n\n");
printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
if(m<0||m>3) return 4;
return m;
}

/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/
void set(int x)/*初始化*/
{
pre[x] = x;
rank[x] = 0;
}

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);
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].str = i;
p[k].end = j;
p[k].dis = arcs[i][j]; /*先把所有城市之间的路段看成一个边*/
}
}
for(i=1;i<=k;i++) /*把所有的边按从小到大进行排序*/
{
index=i;
for(j=i+1;j<=k;j++) if(p[j].dis <p[index].dis) index=j;
temp=p[index];
p[index]=p[i];
p[i]=temp;
}
for(i = 1;i <= k;i ++)
{
if(find(p[i].str) != find(p[i].end))/*如果这两点连接在一起不构成一个回路，则执行下面操作*/
{
printf("\t第%d条路段为：%d--%d,权值为%d\n",++ count,p[i].str,p[i].end,p[i].dis);/*将这条边的起点、终点打印出来*/
ans += p[i].dis; /*说明这条路段要用*/
Union(p[i].str,p[i].end);
}
}
printf("\t遍历所有城市得到最小生成树的代价为: %d\n\n",ans);
}
/*输入城市信息*/
void create( )
{
int i,j;
printf("请输入城市的个数（1—30）:\n");
scanf("%d",&n);
if(n<=0||n>30) {printf("输入错误，请重新输入\n");return ; }
printf("输入%d个城市存储边(带权)的数组（数值范围：1-99，∞用100表示，）:\n",n);
for(i = 1;i <= n;i ++)
{
for(j = 1;j <= n;j ++)
{
scanf("%d",&arcs[i][j]);
if(arcs[i][j]<1||arcs[i][j]>100)
{
printf("输入错误，请重新输入\n");
return ;
}
}
}
for(i=0;i<n;i++)
for(j=0;j<i;j++)
if(arcs[i][j]!=arcs[j][i]) /*判断矩阵是否对称*/
{
printf("输入错误，请重新输入\n");
return ;
}
}
/*显示生成的最小生成树*/
void display( )
{
if(n == 0)
{
printf("这里没有城市之间的信息\n");
return;
}
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] = arcs[1][i]; /*初始化*/
close[i] = 1;
use[i] = 0;
}
for(i = 1;i < n;i ++)
{
int min = 100000000,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] > arcs[k][j])
{
low[j] = arcs[k][j]; /*修改low[]值和close[]值*/
close[j] = k;
}
}
ans += arcs[close[k]][k];
}
if(ans >= 100000000) printf("不能构成最小生成树\n");
else printf("能构成最小生成树\n");
}
/*主函数*/
void main()
{
while(1)
{
switch( menu( ) )
{
case 1:create( );break;/*输入城市信息*/
case 2:judge( );break;/*判断是否能够生成最小生成树*/
case 3:display( );break; /*显示生成的最小生成树*/
case 0:exit( 0 );
default:
printf("输入错误，请重新选择。\n");
break;
}
}
}