广工数据结构课程设计最小生成树.docx
《广工数据结构课程设计最小生成树.docx》由会员分享，可在线阅读，更多相关《广工数据结构课程设计最小生成树.docx（19页珍藏版）》请在冰点文库上搜索。
广工数据结构课程设计最小生成树
课程设计
课程名称数据结构
学院
专业班级
学号
学生姓名
指导教师
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.概要设计
数据类型定义如下：
typedefstructnode
{
intstr;/*起点*/
intend;/*终点*/
intdis;/*距离*/
}node;
nodep[max],temp;/*p记录城市信息*/
intpre[100],rank[100];/*用于判断是否构成回路*/
intn=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（ ） //克鲁斯算法求最小生成树
/*菜单函数*/
intmenu（）
{
intm;
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）return4;
returnm;
}
/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/
voidset（intx）/*初始化*/
{
pre[x]=x;
rank[x]=0;
}
/*找到这个点的祖先*/
intfind（intx）
{
if（x!
=pre[x]）
pre[x]=find（pre[x]）;
returnpre[x];
}
/*将这两个数添加到一个集合里去*/
voidUnion（intx,inty）
{
x=find（x）;
y=find（y）;
if（rank[x]>=rank[y]）
{
pre[y]=x;
rank[x]++;
}
elsepre[y]=x;
}
/*克鲁斯算法求最小生成树*/
voidKruskal（）
{
intans=0,i,j,k=0;/*ans用来记录生成最小树的权总值*/
intindex;
intcount=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].distemp=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）;
}
/*输入城市信息*/
voidcreate（）
{
inti,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;ifor（j=0;jif（arcs[i][j]!
=arcs[j][i]）/*判断矩阵是否对称*/
{
printf（"输入错误，请重新输入\n"）;
return;
}
}
/*显示生成的最小生成树*/
voiddisplay（）{
if（n==0）
{
printf（"这里没有城市之间的信息\n"）;
return;
}
printf（"遍历所有城市得到最小生成树为：
\n\n\n"）;
Kruskal（）;
}
/*判断是否能够生成最小生成树*/
voidjudge（）
{
intclose[100],low[100],i,j,ans=0;/*close[j]表示离j最近的顶点，low[j]表示离j最短的距离*/
intuse[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{
intmin=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"）;
elseprintf（"能构成最小生成树\n"）;
}
/*主函数*/
voidmain（）
{
while
（1）
{
switch（menu（））
{
case1:
create（）;break;/*输入城市信息*/
case2:
judge（）;break;/*判断是否能够生成最小生成树*/
case3:
display（）;break;/*显示生成的最小生成树*/
case0:
exit（）;
default:
printf（"输入错误，请重新选择。
\n"）;
break;
}
}
}
4.调试分析
本课程设计重点在于生成最小生成树算法。
克鲁斯卡尔算法将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去，依次选够（n-1）条边,即得最小生成树。
在克鲁斯卡尔算法中，图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的，该方法对于边相对比较多的不是很实用。
本课程设计为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。
城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。
用a[ i][ j]数组，利用邻接矩阵方式来储存城市与城市间信息 。
5.用户使用说明
按顺序依次输入城市之间的信息，判断是否能构成一个最小生成树，再生成遍历所有城市的最小生成树。
如果输入过程中出现错误，需重新输入。
城市存储边（带权）矩阵中的∞用100表示，矩阵必须对称。
6.测试结果
7.源代码
#include
#include
#include
#definemax100
#defineMAX_LNT30
typedefstructnode/*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以
看成一个边*/
{
intstr;/*起点*/
intend;/*终点*/
intdis;/*距离*/
}node;
nodep[max],temp;/*p记录城市信息*/
intpre[100],rank[100];/*用于判断是否构成回路*/
intn=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/
intmenu（）/*菜单函数*/
{
intm;
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）return4;
returnm;
}
/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/
voidset（intx）/*初始化*/
{
pre[x]=x;
rank[x]=0;
}
intfind（intx）/*找到这个点的祖先*/
{
if（x!
=pre[x]）
pre[x]=find（pre[x]）;
returnpre[x];
}
voidUnion（intx,inty）/*将这两个添加到一个集合里去*/
{
x=find（x）;
y=find（y）;
if（rank[x]>=rank[y]）
{
pre[y]=x;
rank[x]++;
}
elsepre[y]=x;
}
/*克鲁斯算法求最小生成树*/
voidKruskal（）
{
intans=0,i,j,k=0;/*ans用来记录生成最小树的权总值*/
intindex;
intcount=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].distemp=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）;
}
/*输入城市信息*/
voidcreate（）
{
inti,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;ifor（j=0;jif（arcs[i][j]!
=arcs[j][i]）/*判断矩阵是否对称*/
{
printf（"输入错误，请重新输入\n"）;
return;
}
}
/*显示生成的最小生成树*/
voiddisplay（）
{
if（n==0）
{
printf（"这里没有城市之间的信息\n"）;
return;
}
printf（"遍历所有城市得到最小生成树为：
\n\n\n"）;
Kruskal（）;
}
/*判断是否能够生成最小生成树*/
voidjudge（）
{
intclose[100],low[100],i,j,ans=0;/*close[j]表示离j最近的顶点，low[j]表示离j最短的距离*/
intuse[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{
intmin=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"）;
elseprintf（"能构成最小生成树\n"）;
}
/*主函数*/
voidmain（）
{
while
（1）
{
switch（menu（））
{
case1:
create（）;break;/*输入城市信息*/
case2:
judge（）;break;/*判断是否能够生成最小生成树*/
case3:
display（）;break;/*显示生成的最小生成树*/
case0:
exit（0）;
default:
printf（"输入错误，请重新选择。
\n"）;
break;
}
}
}
升级会员 