当前位置:首页 >> 其它课程 >>

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


课 程 设 计 报 告

课程设计名称:数据结构课程设计 课程设计题目:最小生成树 Kruskal 算法

院(系): 专 班 学 姓 业: 级: 号: 名:

指导教师:





1 课程设计介绍 ...........................

................................................................................. 1 1.1 课程设计内容 ....................................................................................................... 1 1.2 课程设计要求 ....................................................................................................... 1 2 课程设计原理 ............................................................................................................ 2 2.1 课设题目粗略分析 ............................................................................................... 2 2.2 原理图介绍 ......................................................................... 错误!未定义书签。 2.2.1 功能模块图 ................................................................. 错误!未定义书签。 2.2.2 流程图分析 ................................................................................................... 5 3 数据结构分析 .......................................................................................................... 12 3.1 存储结构 ............................................................................................................. 12 3.2 算法描述 ............................................................................................................. 12 4 调试与分析 .............................................................................................................. 14 4.1 调试过程 ............................................................................................................. 14 4.2 程序执行过程 ..................................................................................................... 14 参考文献 ........................................................................................................................ 17 附 录(关键部分程序清单) .................................................................................. 18

I

1
1.1 课程设计内容

课程设计介绍

编写算法能够建立带权图,并能够用 Kruskal 算法求该图的 最小生成树。 最小生成树能够选择图上的任意一点做根结点。 最小 生成树输出采用顶点集合和边的集合的形式。

1.2 课程设计要求
1. 顶点信息用字符串,数据可自行设定。 2. 参考相应的资料,独立完成课程设计任务。 3. 交规范课程设计报告和软件代码。

1

2
2.1 课设题目粗略分析

课程设计原理

根据课设题目要求,拟将整体程序分为三大模块。以下是三个模 块的大体分析: 1. 要确定图的存储形式,通过对题目要求的具体分析。发现该题 的主要操作是路径的输出,因此采用边集数组(每个元素是一个结构 体,包括起点、终点和权值)和邻接矩阵比较方便以后的编程。 2. Kruskal 算法。该算法设置了集合 A,该集合一直是某最小生 成树的子集。在每步决定是否把边(u,v)添加到集合 A 中,其添加条 件是 A∪{(u,v)}仍然是最小生成树的子集。我们称这样的边为 A 的 安全边,因为可以安全地把它添加到 A 中而不会破坏上述条件。 3. Dijkstra 算法。算法的基本思路是:假设每个点都有一对标号 (dj,pj),其中 d 是从起源点到点 j 的最短路径的长度(从顶点到其本 身的最短路径是零路(没有弧的路) ,其长度等于零) ;pj 则是从 s 到 j 的最短路径中 j 点的前一点。 求解从起源点 s 到点 j 的最短路径算法的 基本过程如下: 1)初始化。 起源点设置为: ①ds=0,ps 为空; ②所有其它点: di=∞,pi=?; ③标记起源点 s,记 k=s,其他所有点设为未标记的。 2)k 到其直接连接的未标记的点 j 的距离,并设置: dj=min[dj, dk+lkj]
2

式中,lkj 是从点 k 到 j 的直接连接距离。 3)选取下一个点。从所有未标记的结点中,选取 dj 中最小的一个 i: di=min[dj, 所有未标记的点 j] 点 i 就被选为最短路径中的一点,并设为已标记的。 4)找到点 i 的前一点。从已标记的点中找到直接连接到 i 的点 j*,作 为前一点,设置: i=j*

5)标记点 i。如果所有点已标记,则算法完全推出,否则,记 k=i,转 到 2)再继续。 而程序中求两点间最短路径算法。其主要步骤是: ① 调用 dijkstra 算法。
② 将 path 中的第 “终点” 元素向上回溯至起点, 并显示出来。

(1)预处理 #include<stdio.h> #define typedef maxvertexnum 20 #define maxedgenum 40

int adjmatrix[maxvertexnum][maxvertexnum]; (2)定义一个储 存节点信息的结构体 struct edgenode { int frontvex; int rearvex; int weight; };

typedef edgenode adgeset[maxedgenum]; (3)初始化的无向图,将每条边的权值赋值为无穷 void insitadj(adjmatrix &GA) {
3

输入需要架设网络的城市的数目 输入需要架设网络的各个城市之间的距离 找到一个最小的生成树 输出一个最小的生成树这个最小的生成树就是一个架设网络的最优解

for(int i=1;i<maxvertexnum;i++) j=1;j<maxvertexnum;j++) { GA[i][j]=20000; } } }

{

for(int //将边的权

值赋值为无穷//

(4)以各个城市为基础建立一个网络 void setadj(adjmatrix &GA,int n) //建立网络 { for(int i=1;i<=n+1;i++) { { for(int j=i+1;j<n+1;j++)

printf("请输入第%d 个城市到第%d 个城市的距离:",i,j); scanf("%d",&GA[i][j]); for(i=1;i<=n+1;i++) { { } }

for(int j=i+1;j<n+1;j++) } } }

GA[j][i]=GA[i][j];

4

开始

输入顶点个数 n 输入边数 e

输入边集 显示菜单,进行 选择。

结束

Kruskal 算法

求两点间最短距 离

求两点间最短距 离

图 2.1 功能模块图

2.2.2 流程图分析 1. 主函数

5

开始

输入顶点个数 n 输入边数 e 输入选项 a

a=1

a=2

a=3

调用 insertsort, kruskal 函数

输入 v0 调用 dijkstra , printpath1 函数

输入 v0,v1 调 用 dijkstra , printpath2 函数

输入 a=4

结束

图 2.2 主函数流程图

2. insertsort 函数

6

开始

int i,j for(i=2;i<=e;i++)

Y

ge[i].w< ge[i-1]. w

N

ge[0]=ge[i]; j=i-1;
N

ge[0]. w<ge[j ].w
Y

ge[j+1]=ge[j]; j--;

ge[j+1]=ge[0];

结束

3.

图 2.3 insertsort 函数流程图

7

3.Kruskal 函数
开始

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
Y

v1=seeks(set,ge[j].bv); v2=seeks(set,ge[j].tv);

N

v1!=v2

Y printf("(%d,%d):%d\n",ge[j].bv,g e[j].tv,ge[j].w); set[v1]=v2; i++;

N

j++;

结束 图 2.4 Kruskal 函数流程图

8

4. dijkstra 函数
开始

int u,vnum,w,wm; for(w=1;w<=n;w++) {dist[w]=cost[v0][w]; if(cost[v0][w]<32767) path[w]=v0;}vnum=1;

vnum<n-1
Y N

wm=32767; u=v0; for(w=1;w<=n;w++) if(s[w]==0&&dist[w]<wm) {u=w;wm=dist[w];} s[u]=1;vnum++;
for(w=1;w<=n;w++) if(s[w]==0&&dist[u]+cost[u][w]<dist[w] &&cost[u][w]!=32767) {dist[w]=dist[u]+cost[u][w];path[w]=u;}

结束

图 2.5 dijkstra 函数流程图

9

5. printpath1 函数

开始

int i,k; for(i=1;i<=n;i++)

s[i]==1
Y

N

k=i; while(k!=v0){ printf("%d<-",k); k=path[k];} printf("%d:%d\n",k,dist[i]);

printf("%d<-%d:3276 7\n",i,v0);

结束

图 2.6 printpath1 函数流程图

10

6. printpath2 函数

开始

int k; k=v1; while(k!=v0) {printf("%d<-",k);k=path[k];} printf("%d:%d\n",k,dist[v1]); 结束

图 2.7 printpath2 函数流程图

11

3
3.1 存储结构

数据结构分析

定义一个结构体数组, 其空间足够大, 可将输入的字符串存于数组中。 struct edges {int bv; int tv; int w; };

3.2 算法描述
1. Kruskal 函数: 因为 Kruskal 需要一个有序的边集数组,所以要先对边集数组 排序。其次,在执行中需要判断是否构成回路,因此还需另有一个判 断函数 seeks,在 Kruskal 中调用 seeks。 2. dijkstra 函数: 因为从一源到其余各点的最短路径共有 n-1 条, 因此可以设一 变量 vnum 作为计数器控制循环。该函数的关键在于 dist 数组的重新 置数。该置数条件是:该顶点是被访问过,并且新起点到该点的权值 加上新起点到源点的权值小于该点原权值。因此第一次将其设为:if (s[w]==0&&cost[u][w]+dist[u]<dist[w]) 。但是在实际运行中,发现有
12

些路径的权值为负。经过分析发现,因为在程序中∞由 32767 代替。 若 cost[u][w]==32767,那么 cost[u][w]+dist[u]肯定溢出主负值,因此 造成权值出现负值。但是如果 cost[u][w]==32767,那么 dist[w]肯定不 需 要 重 新 置 数 。 所 以 将 条 件 改 为 :

if(s[w]==0&&cost[u][w]+dist[u]<dist[w]&&cost[u][w]!=32767)。修改之 后问题得到解决。 3. printpath1 函数: 该函数主要用来输出源点到其余各点的最短路径。 因为在主函 数调用该函数前,已经调用了 dijkstra 函数,所以所需的 dist、path、s 数组已经由 dijkstra 函数生成, 因此在该函数中, 只需用一变量控制循 环,一一将 path 数组中的每一元素回溯至起点即可。其关键在于不同 情况下输出形式的不同。 4. printpath2 函数: 该函数主要用来输出两点间的最短路径。其主要部分与 printpath1 函 数相同,只是无需由循环将所有顶点一一输出,只需将 path 数组中下 标为 v1 的元素回溯至起点并显示出来。

13

4
4.1 调试过程

调试与分析

在调试程序时主要遇到一下几类问题: 1. 有时函数中一些数组中的数据无法存储。 2. 对其进行检验发现没有申请空间大小。 3. 在源程序的开头用#define 定义数值大小, 在使用数组时亦可知 道它的空间大小。 4. 此函数中有时出现负值。 5. 对 其 进 行 检 验 发 现 在 程 序 中 ∞ 由 32767 代 替 。 若 cost[u][w]==32767,那么 cost[u][w]+dist[u]肯定溢出主负值,因此造成 权值出现负值。 6. 但是当 cost[u][w]==32767,那么 dist[w]肯定不需要重新置数。 所 以 将 if ( s[w]==0&&cost[u][w]+dist[u]<dist[w] ) 改 为 :

if(s[w]==0&&cost[u][w]+dist[u]<dist[w]&&cost[u][w]!=32767)。问题得 到解决。

1.2 程序执行过程
系统使用说明: 1. 输入的数据可以是整数,字符串(如 1,2,3) ; 2. 本系统可以建立带权图,并能够用 Kruskal 算法求改图的最小

14

生成树。而且能够选择图上的任意一点做根结点。还能够求两点之间 的最短距离。 3. 该系统会有菜单提示,进行选项: 1.kruskal 2.shortpath 3.shortpath between two point 4.exit 4.程序实际运行截图

图 4.1 输入形式

15

图 4.2 kruskal 算法输出

图 4.3 最短距离输出

16

错误!未指定书签。

参考文献
[1] 《数据结构》 (C 语言版) .严蔚敏 , 吴伟民.清华大学出版社.2007 [2]《算法设计与分析》.张德富.国防工业出版社.2009 [3]《计算机算法与程序设计》.朱青.清华大学出版社.2009 [4]《C 程序设计语言》.徐宝文,李志.机械工业出版社.2004

17

错误!未指定书签。


程序代码 #include"stdio.h" #define MAXE 100 struct edges {int bv; int tv; int w; };

录(关键部分程序清单)

typedef struct edges edgeset; int seeks(int set[],int v) { int i; i=v; while(set[i]>0) i=set[i]; return i; } void kruskal(edgeset ge[],int n,int e)

18

错误!未指定书签。

{ int set[MAXE],v1,v2,i,j; for(i=1;i<n+1;i++) set[i]=0; i=1; j=1; while(j<=e&&i<=n-1) { v1=seeks(set,ge[j].bv); v2=seeks(set,ge[j].tv); if(v1!=v2) { printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w); set[v1]=v2; i++; } j++; } } void insertsort(edgeset ge[],int e) {

19

错误!未指定书签。

int i,j; for(i=2;i<=e;i++) if(ge[i].w<ge[i-1].w) { ge[0]=ge[i]; j=i-1; while(ge[0].w<ge[j].w) { ge[j+1]=ge[j]; j--; } ge[j+1]=ge[0]; } } void dijkstra(int cost[MAXE][MAXE],int dist[MAXE],int

path[MAXE],int s[MAXE],int n,int v0) { int u,vnum,w,wm; for(w=1;w<=n;w++) { dist[w]=cost[v0][w];

20

错误!未指定书签。

if(cost[v0][w]<32767) path[w]=v0; } vnum=1; while(vnum<n-1) { wm=32767; u=v0; for(w=1;w<=n;w++) if(s[w]==0&&dist[w]<wm) { u=w; wm=dist[w]; } s[u]=1; vnum++; for(w=1;w<=n;w++) if(s[w]==0&&dist[u]+cost[u][w]<dist[w]&&cost[u][w]!=32767) { dist[w]=dist[u]+cost[u][w]; path[w]=u;

21

错误!未指定书签。

} } } void printpath1(int dist[],int path[],int s[],int n,int v0) { int i,k; for(i=1;i<=n;i++) if(s[i]==1) { k=i; while(k!=v0) { printf("%d<-",k); k=path[k]; } printf("%d:%d\n",k,dist[i]); } else printf("%d<-%d:32767\n",i,v0); } void printpath2(int dist[],int path[],int v0,int v1)

22

错误!未指定书签。

{ int k; k=v1; while(k!=v0) { printf("%d<-",k); k=path[k]; } printf("%d:%d\n",k,dist[v1]); } main() { edgeset ge[MAXE]; int cost[MAXE][MAXE],dist[MAXE],path[MAXE],s[MAXE],a,n,e,i,j,k,v0,v 1; printf("请输入顶点个数:"); scanf("%d",&n); printf("请输入边的条数:"); scanf("%d",&e); printf("请输入边的信息(起点,终点,权值):\n");

23

错误!未指定书签。

for(i=1;i<=e;i++) scanf("%d,%d,%d",&ge[i].bv,&ge[i].tv,&ge[i].w); printf("在下列菜单中进行选择:\n"); printf("1.kruskal 算法( (起点,终点)权值) :\n"); printf("2.shortpath(终点<-起点) :\n"); printf("3.shortpath between two point(终点<-起点) :\n"); printf("4.exit(退出) :\n"); scanf("%d",&a); while(a!=4) { switch(a) { case 1:insertsort(ge,e); kruskal(ge,n,e); break; case 2:printf("请输入起始顶点序号:"); scanf("%d",&v0); for(i=1;i<=n;i++) for(j=1;j<=n;j++) cost[i][j]=32767; for(k=1;k<=e;k++)

24

错误!未指定书签。

{ i=ge[k].bv; j=ge[k].tv; cost[i][j]=ge[k].w; } for(i=1;i<=n;i++) s[i]=0; s[v0]=1; dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0); break; case 3:printf("请输入起始顶点序号:"); scanf("%d",&v0); printf("请输入终点序号:"); scanf("%d",&v1); for(i=1;i<=n;i++) for(j=1;j<=n;j++) cost[i][j]=32767; for(k=1;k<=e;k++) { i=ge[k].bv;

25

错误!未指定书签。

j=ge[k].tv; cost[i][j]=ge[k].w; } for(i=1;i<=n;i++) s[i]=0; s[v0]=1; dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1); break; } printf("在下列菜单中进行选择:\n"); printf("1.kruskal 算法( (起点,终点)权值) :\n"); printf("2.shortpath(终点<-起点) :\n"); printf("3.shortpath between two point(终点<-起点) :\n"); printf("4.exit(退出) :\n"); scanf("%d",&a); } return 1; }

26

课程设计总结: 本次课程设计涉及到的范围很广, 让本人能够比较系统的对 C 语言和数据结 构进行一次整理和复习。同时有了很多的体会和经验。 1. 巩固了以前学过的 C 语言的知识,在这次课程设计中我体会到 C 语言超 强的逻辑性,能够熟练使用 VC++的编译环境,也对这两门课程有了新的认识, 他们既有联系,又相互区别,在编写程序过程中要灵活应用 2. 对数据结构的理解有待加强,算法的知识面也有待于提高。不同的人会 选择不同的算法,所以即使同样的程序,不同的人必然会设计出不同的方案,所 以以后的学习生活中,一定要广泛涉猎,掌握更多更好的解决问题的方法。 3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的,没有平 时基础的训练是不会写出高效的算法。 4. 此次课程设计时间虽短, 课设的过程是短暂的, 但我所收获的是永恒的。 它让我尝到了学习的快乐,成功的喜悦,更让我懂得了不少做人的道理。要完成 一项任务或把东西学好就必须有足够的信心, 持久的耐心, 有面对困难无所畏惧 的精神,这对我日后的学习和生活产生了深远一个影响。

指导教师评语:

指导教师(签字):







课程设计成绩

27


相关文章:
最小生成树数据结构课程设计报告
Z110702301 计算机 113 班 数据结构课程设计 2 01 3—2 014 学年第 2 学期...程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析主模块:用于...
数据结构课程设计最小生成树的构建实验报告
数据结构课程设计最小生成树的构建实验报告_工学_高等教育_教育专区。《数据结构...()//构造算法 { t=0;//初始化边的个数为 0 t1=1; T1[1]=1; //...
数据结构课程设计最小生成树问题
数据结构算法 课程设计报告 课程设计报告课程设计题目: 课程设计题目: 题目 专业班级: 专业班级: 姓名: 最小生成树问题 信息与计算科学 1001 信息与计算科学 ...
最小生成树求解-数据结构与算法课程设计报告
用 -1- 数据结构算法课程设计报告 2 问题分析和任务定义本课程设计重在使用 prim 算法实现任意给定的网和起点的图的所有最小生成树的求 解,实现本课程设计的...
广工数据结构课程设计最小生成树
广工数据结构课程设计最小生成树_工学_高等教育_教育专区。课程设计 课程名称 ...[y] = x; } /*克鲁斯算法最小生成树*/ void Kruskal( ) { int ans ...
数据结构课程设计-最小生成树问题
算法求最小生成树|\n"); printf("| 2.用 kruskal 算法最小生成树|\n"...数据结构课程设计报告(最... 17页 3下载券 数据结构课程设计报告(最... 21...
最小生成树数据结构实验报告
最小生成树数据结构实验报告_计算机软件及应用_IT/计算机_专业资料。摘 要 最...本课程设计是以邻接矩阵作为图的存储结构,分别采用 Prim 和 Kruskal 算法 求最...
数据结构实验报告-最小生成树
数据结构实验报告-最小生成树_调查/报告_表格/模板_实用文档。电子科技大学 实...数据结构与算法—图三、实验学时:4 四、实验原理: Kruskal 算法是一种按照图...
《数据结构》课程设计报告N个城市最小生成树
数据结构课程设计报告N个城市最小生成树_计算机软件及应用_IT/计算机_专业...用 Prim 算法或 Kruskal 算 法建立最小生成树, 并计算得到的最小生成树的...
最小生成树课程设计
数据结构课程设计报告(最... 21页 2下载券 最小生成树问题课程设计... 11页...本课程设计 是以邻接矩阵作为图的存储结构,分别采用 Prim 和 Kruskal 算法求最...
更多相关标签:
最小生成树kruskal | kruskal求最小生成树 | 最小生成树之kruskal | 最小生成树算法 | 最小生成树的算法 | prim算法求最小生成树 | 最小生成树prim算法 | 普里姆算法最小生成树 |