数据结构课程设计报告最小生成树kruskal算法.doc

课程设计报告
课程设计名称:数据结构课程设计
课程设计题目:最小生成树Kruskal算法
院(系):
专业:
班级:
学号:
姓名:
指导教师:
目录
1 课程设计介绍 1
课程设计内容 1
课程设计要求 1
2 课程设计原理 2
课设题目粗略分析 2
原理图介绍 4
功能模块图 4
流程图分析 5
3 数据结构分析 11
存储结构 11
算法描述 11
4 调试与分析 13
调试过程 13
程序执行过程 13
参考文献 16
附录(关键部分程序清单) 17
1 课程设计介绍
课程设计内容
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
课程设计要求
顶点信息用字符串,数据可自行设定。
参考相应的资料,独立完成课程设计任务。
交规范课程设计报告和软件代码。
2 课程设计原理
课设题目粗略分析
根据课设题目要求,拟将整体程序分为三大模块。以下是三个模块的大体分析:
要确定图的存储形式,通过对题目要求的具体分析。发现该题的主要操作是路径的输出,因此采用边集数组(每个元素是一个结构体,包括起点、终点和权值)和邻接矩阵比较方便以后的编程。
Kruskal算法。该算法设置了集合A,该集合一直是某最小生成树的子集。在每步决定是否把边(u,v)添加到集合A中,其添加条件是A∪{(u,v)}仍然是最小生成树的子集。我们称这样的边为A的安全边,因为可以安全地把它添加到A中而不会破坏上述条件。
Dijkstra算法。算法的基本思路是:假设每个点都有一对标号(dj,pj),其中d是从起源点到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下:
初始化。起源点设置为:①ds=0,ps为空;②所有其它点:di=∞,pi=?;③标记起源点s,记k=s,其他所有点设为未标记的。
k到其直接连接的未标记的点j的距离,并设置:
dj=min[dj, dk+lkj]
式中,lkj是从点k到j的直接连接距离。
选取下一个点。从所有未标记的结点中,选取dj中最小的一个i:
di=min[dj, 所有未标记的点j]
点i就被选为最短路径中的一点,并设为已标记的。
4)找到点i的前一点。从已标记的点中找到直接连接到i的点j*,作为前一点,设置: i=j*
5)标记点i。如果所有点已标记,则算法完全推出,否则,记k=i,转到2)再继续。
而程序中求两点间最短路径算法。其主要步骤是:
调用dijkstra算法。
将path中的第“终点”元素向上回溯至起点,并显示出来。

原理图介绍
功能模块图
开始
输入顶点个数n
输入边数e
输入边集
显示菜单,进行选择。
求两点间最短距离
求两点间最短距离
Kruskal算法
结束
功能模块图
流程图分析
主函数
开始
输入顶点个数n
输入边数e
输入选项a
a=1
调用insertsort,kruskal函数
a=2
输入v0
调用dijkstra,printpath1函数
a=3
输入v0,v1
调用dijkstra,printpath2函数
输入a=4
结束
主函数流程图
insertsort函数
开始
int i,j
for(i=2;i<=e;i++)
ge[i].w<ge[i-1].w
ge[0]=ge[i];
j=i-1;
ge[0].w<ge[j].w
ge[j+1]=ge[j];
j--;
Y
ge[j+1]=ge[0];
N
Y
结束
N
insertsort函数流程图

开始
int set[MAXE],v1,v2,i,j;
for(i=1;i<n+1;i++)
set[i]=0;
i=1;
j=1;
j<=e&&i<=n-1
v1!=v2
v1=seeks(set,ge[j].bv);
v2=seeks(set,ge[j].tv);
printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);
set[v1]=v2;
i++;
j++;
Y
Y
结束
N
N
Kruskal函数流