当前位置:首页 >> 其它课程 >> 数据结构,最小生成树克鲁斯卡尔算法的实现

数据结构,最小生成树克鲁斯卡尔算法的实现






设计了一个用 C/C++编写程序实现克鲁斯卡尔最小生成树算 法,该程序操作简单,界面清晰,易于为用户所接受。
关键词:克鲁斯卡尔,邻接矩阵,最小生成树,vc++。





1 课题描述..................................

..................................................................................................... 1 2 问题分析和任务定义 ................................................................................................................... 2 3 逻辑设计....................................................................................................................................... 3 4 详细设计....................................................................................................................................... 4 5 程序编码..................................................................................................................................... 11 6 程序调试与测试......................................................................................................................... 17 7 结果分析..................................................................................................................................... 19 8 总结............................................................................................................................................. 20 参考文献......................................................................................................................................... 21

1 课题描述
用 C/C++编写程序实现克鲁斯卡尔最小生成树算法。 假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要 n-1 条线路。 这是我们设计一个最小生成树的程序用来算出最节省经费的前提下 建立这个通信站。

1

2 问题分析和任务定义
假设连通网 N=(V,{E}),则令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T=(V,{}),图中每个顶点自成一个连通分 量。在 E 中选择代价最小的边,若该边依附的顶点落在 T 中不同的 连通分量上,则将此边加入到 T 中,否则舍去此边而选择下一条代 价最小的边。依次类推,直到 T 中所有顶点都在同一连通分量上为 止。

2

3 逻辑设计
设计思想: 采用邻接矩阵来存储图,然后采用克鲁斯卡尔算法 求出最小生成树。

结构体定义

函数模块一 (图的创建) 采用邻接矩阵做存储结构

函数模块二 (求最小生成树) 克鲁斯卡尔算法

主函数引用函数模块一、二,实现 算法设计

1) .定义结构体。 2) .采用邻接矩阵做存储结构创建图(函数模块一) 。 3) .采用克鲁斯卡尔算法求出该图的最小生成树(函数模块二) 。 4) .在主函数里面分别调用以上各个函数,最终实现设计目的。

3

4 详细设计
4.1.程序结构 ·函数 CreateMGraph 用来实现图的创建,以及图的相关信息的存储。图的存储采用 邻接矩阵存储结构。 ·函数 minitree_KRUSKAL 用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁 斯卡尔算法可以实现,本段代码使用的是克鲁斯卡尔算法,这也是 本题所要求使用的。 ·各个函数间的联系 先 调 用 函 数 CreateMGraph 实 现 图 的 创 建 , 然 后 调 用 函 数 minitree_KRUSKAL 求出该图的最小生成树 4.2.设计说明 ·在开始的时候添加一些限制条件方便函数的功能实现例如: #define MaxVertexNum 100 //最大顶点个数 #define QueueSize 30 #define M 30 ·模块一:图的创建 ·结构体定义为: typedef struct { VertexType vexs[MaxVertexNum]; //顶点表 Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的 相连接的两个顶点 int n,e; //图中当前的顶点数和边 数 }MGraph; ·函数定义为: MGraph CreateMGraph() {
4

MGraph G; int i,j,k,ch3; char ch1,ch2; printf("请输入该图的顶点数和边数:\n"); scanf("%d,%d",&(G.n),&(G.e)); printf("请输入该图的顶点信息:\n"); for(i=1;i<=G.n;i++) { getchar(); scanf("%c",&(G.vexs[i])); } for(i=1;i<=G.n;i++) for(j=1;j<=G.n;j++) G.edges[i][j].w=0; printf(" 请 输 入 该 图 每 条 边 对 应 的 两 个 顶 点 的 名 称:\n"); for(k=1;k<=G.e;k++) { scanf("%c",&ch1); printf("请输入第%d 条边的顶点序号:",k); scanf("%c %c",&ch1,&ch2); printf("请输入第%d 条边的权值大小:",k); scanf("%d",&ch3); for(i=1;ch1!=G.vexs[i];i++); for(j=1;ch2!=G.vexs[j];j++); e[p].vexh=i; e[p].vext=j; e[p].weight=G.edges[i][j].w=ch3; //权值 e[p].flag=0; p++; } return G; }
5

流程如图 4.1 所示 创建图使用的是函数 MGraph CreateMGraph(),该图的存储结 构是邻接矩阵,先对图的结构体进行定义,再进行初始化。在函数 中需要手动输入图的参数(如顶点数、边数、顶点信息、相连接的 顶点、边的权值等)用来建立图并且确定图的邻接矩阵。最后在完 成图的信息输入即建立图以后输出图的邻接矩阵表。 ·模块二:求图的最小生成树。 void minitree_KRUSKAL(MGraph *G) { int i,min,j,k; VEX t[M]; for(i=1;i<=G->n;i++) { t[i].data=G->vexs[i]; t[i].jihe=i; } i=1; while (i<G->n) { min=MaxVertexNum; for (j=0;j<G->e;j++) { if (e[j].weight<min&&e[j].flag==0) { min=e[j].weight;
6

k=j; } } if (t[e[k].vexh].jihe!=t[e[k].vext].jihe) { e[k].flag=1; for (j=1;j<=G->n;j++) if (t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++; } } printf("克鲁斯卡尔最小生成树:\n"); for (i=0;i<G->e;i++) if (e[i].flag==1) else e[k].flag=2;

printf("(%d,%d) %d\n",e[i].vexh,e[i].vext,e[i].weight);//输 出最小生成树 } 该步骤应用的是克鲁斯卡尔算法,它的基本思想是:每次选不 属于同一连通分量(保证不生成圈)且边权值最小的顶点,将边加入 MST(Minimum Spanning Tree 最小生成树) ,并将所在的 2 个连通分 量合并,直到只剩一个连通分量。
7

流程如图 4.2 所示。

8

开始
请输入该 图的顶点 数和边数

G.e>(G.n1)*G.n/2

输入错 误,请重 新输入 请输入该 图的顶点 信息

i=1

i<=G.n i++ getchar(); scanf("%c",& (G.vexs[i]))

i=1

i++

i<=G.n

j=1

j<=G.n j++ G.edges[i] [j].w=0

请输入该图每 条边对应的两 个顶点的名称

K=1

k<=G.e

K++

请输入第%d条边的顶点 序号 请输入第%d条边的权值 大小

i=1

ch1!=G.vexs [i]

j=1

i++

ch2!=G.vexs[j] return G j++ e[p].vexh=i; e[p].vext=j; e[p].weight=G.edges[i][j].w=ch3; //权值 e[p].flag=0; p++;

结束

图 4.1
9

开始

i=1 i++ i<=G->n

t[i].data=G>vexs[i]; t[i].jihe=i;

i=1

i<G->n

min=MaxVertexNum; j=0 j++ j<G->e

e[j].weight<min&& e[j].flag==0

min=e[j].weight; k=j;

t[e[k].vexh].jihe! =t[e[k].vext].jihe

N

e[k].flag=2

e[k].flag=1

j=1 j++ j<=G->n

t[j].jihe==t[e[k] .vext].jihe

t[j].jihe=t[e[k].vexh ].jihe; t[e[k].vext].jihe=t[e [k].vexh].jihe; i++;

i=0 i++ i<G->e

e[i].flag==1

输出最小 生成树

结束

图 4.2
10

5 程序编码
#include <stdio.h> #define MaxVertexNum 100 #define M 30 typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; typedef char VertexType; typedef int EdgeType; typedef struct Lnode { int w;//相应一条边的权值 }Link; typedef struct { VertexType vexs[MaxVertexNum]; //顶点表 //访问标志数组 //最大顶点个数

Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的相连 接的两个顶点 int n,e; }MGraph; typedef struct { char data;
11

//图中当前的顶点数和边数

int jihe; }VEX; typedef struct { int vexh,vext; //边顶点 int weight; int flag; }EDGE; EDGE e[M]; int p=0; /************************* **************************/ MGraph CreateMGraph() { MGraph G; int i,j,k,ch3; char ch1,ch2; printf("请输入该图的顶点数和边数:\n"); scanf("%d,%d",&(G.n),&(G.e)); while(G.e>(G.n-1)*G.n/2) { printf("输入错误,请重新输入:\n");
12

//权值 //标记

















scanf("%d,%d",&(G.n),&(G.e)); } printf("请输入该图的顶点信息:\n"); for(i=1;i<=G.n;i++) { getchar(); scanf("%c",&(G.vexs[i])); } for(i=1;i<=G.n;i++) for(j=1;j<=G.n;j++) G.edges[i][j].w=0; printf("请输入该图每条边对应的两个顶点的名称:\n"); for(k=1;k<=G.e;k++) { scanf("%c",&ch1); printf("请输入第%d 条边的顶点序号:",k); scanf("%c %c",&ch1,&ch2); printf("请输入第%d 条边的权值大小:",k); scanf("%d",&ch3); for(i=1;ch1!=G.vexs[i];i++); for(j=1;ch2!=G.vexs[j];j++); e[p].vexh=i;
13

e[p].vext=j; e[p].weight=G.edges[i][j].w=ch3; //权值 e[p].flag=0; p++; } return G; } /************************* 克 鲁 斯 卡 尔 最 小 生 成 树 *************************/ void minitree_KRUSKAL(MGraph *G) { int i,min,j,k; VEX t[M]; for(i=1;i<=G->n;i++) { t[i].data=G->vexs[i]; t[i].jihe=i; } i=1; while (i<G->n) { min=MaxVertexNum;
14

for (j=0;j<G->e;j++) { if (e[j].weight<min&&e[j].flag==0) { min=e[j].weight; k=j; } } if (t[e[k].vexh].jihe!=t[e[k].vext].jihe) { e[k].flag=1; for (j=1;j<=G->n;j++) if (t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++; } else e[k].flag=2; } printf("克鲁斯卡尔最小生成树:\n"); for (i=0;i<G->e;i++) if (e[i].flag==1)
15

printf("(%d,%d) %d\n",e[i].vexh,e[i].vext,e[i].weight);//输 出最小生成树 }

/****************************











**********************************/ int main() { MGraph G; printf("\n"); printf("************************************************** ********\n"); printf("*** ***\n"); printf("************************************************** ********\n"); G=CreateMGraph(); minitree_KRUSKAL(&G); return 0; } //建立该图的邻接矩阵 //克鲁斯卡尔算法最小生成树 克鲁斯卡尔算法求图的最小生成树

16

6 程序调试与测试
运行程序后如图所示

图 6.1

输入错误数组后如图所示

图 6.2

17

继续输入正确数组后如图所示

图 6.3

18

7 结果分析
程序运行时如果输入的点大于边减一再乘以边除以 2, 那就是说 输入的数组是错误的,此时程序提醒输入错误,在重新输入。如果 输入正确那么程序会输出最小生成树。

19

8 总结
这个程序运用函数 CreateMGraph 来实现图的创建, 以及图的相 关信息的存储。图的存储采用邻接矩阵存储结构。 在运用函数 minitree_KRUSKAL 来求图的最小生成树。图的最小生成树有普利姆 算法和克鲁斯卡尔算法可以实现,本段代码使用的是克鲁斯卡尔算 法,这也是本题所要求使用的。在整个程序中先调用函数 CreateMGraph 实现图的创建, 然后调用函数 minitree_KRUSKAL 求出 该图的最小生成树。 这个程序实现了最小生成树的生成。在整个程序的设计过程中 有太多的错误以及不懂的地方,虽然在最后完成了程序设计,但是 我发现了我的更多的不足,在以后的学习中我会更加努力。

20

参考文献 [1] 严蔚敏,吴伟民.数据结构(C 语言版)[M].北京:清华大学出版 社,2002 [2] 李春葆.数据结构(C 语言版)习题与解析[M]. 北京: 清华大学出 版社,2002 [3] 钱能.C++程序设计教程[M]. 北京:清华大学出版社,2003

21


更多相关文档:

数据结构,最小生成树克鲁斯卡尔算法的实现

数据结构,最小生成树克鲁斯卡尔算法的实现_其它课程_高中教育_教育专区。数据结构课程设计 摘 要 设计了一个用 C/C++编写程序实现克鲁斯卡尔最小生成树算 法,该...

数据结构实习报告 克鲁斯卡尔算法生成的最小生成树

数据结构实习报告 克鲁斯卡尔算法生成的最小生成树_计算机软件及应用_IT/计算机_...克鲁斯卡尔算法求最小生... 3页 1下载券 克鲁斯卡尔算法实现最小... 4页 ...

最小生成树克鲁斯卡尔算法的实现

课程设计任务书 2011—2012 学年 第一学期 —专业: 计算机科学与技术 课程设计名称: 设计题目: 学号: 数据结构课程设计 最小生成树克鲁斯卡尔算法的实现 2011 年...

7.最小生成树克鲁斯卡尔算法的实现任务书

算法 的时间、空间复杂性分析; 7)编写课程设计报告; 3.参考资料 数据结构课程设计 最小生成树克鲁斯卡尔算法的实现 自 2014 年 2 月 24 日至 2014 年 3 月...

【数据结构】普里母算法和克鲁斯卡尔方法求最小生成树完整程序

数据结构】普里母算法克鲁斯卡尔方法求最小生成树完整程序_IT/计算机_专业资料。【数据结构】普里母算法克鲁斯卡尔方法求最小生成树完整程序,直接在vc或vs里...

克鲁斯卡尔(Kruskal)算法求无向网的最小生成树数据结构报告

数据结构 上机报告(1) 姓名:张可心 学号:14030188030 班级:1403018 一、题目描述 用克鲁斯卡尔(Kruskal)算法求无向网的最小生成树,分 析你的算法的时空复杂度,...

克鲁斯卡尔算法实现最小生成树

克鲁斯卡尔算法实现最小生成树_工学_高等教育_教育专区。数据结构克鲁斯卡尔算法姓名: 学号: 班级:信工 0808 成绩: 1,原理 ,由于克鲁斯卡尔算法是在图中从边长小...

克鲁斯卡尔算法求最小生成树

克鲁斯卡尔算法最小生成树_计算机软件及应用_IT/计算机_专业资料。数 据 结 ...二、目的:本实验通过实现最小生成树的算法,使学生理解图的数据结构存储表 示,...

课程设计---克鲁斯卡尔算法求最小生成树

调试与操作说明 4.1 测试结果:如下图 图 2 测试结果 1 11 图 3 测试结果 2 4.2 调试分析 本程序利用克鲁斯卡尔算法最小生成树数据结构清晰因而条是比较顺利...

克鲁斯卡尔算法求最小生成树

调试与操作说明 4.1 测试结果:如下图 图 2 测试结果 1 9 图 3 测试结果 2 4.2 调试分析 本程序利用克鲁斯卡尔算法最小生成树数据结构清晰因而调试比较顺利...
更多相关标签:
克鲁斯卡尔算法实现 | 克鲁斯卡尔算法 | 克鲁斯卡尔算法代码 | 克鲁斯卡尔算法流程图 | 克鲁斯卡尔算法 c | 克鲁斯卡尔算法 java | 克鲁斯卡尔算法 c语言 | 克鲁斯卡尔算法复杂度 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com