《克鲁斯卡尔最小生成树》由会员分享，可在线阅读，更多相关《克鲁斯卡尔最小生成树（17页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告构造可以使 n 个城市连接的最小生成树课程名称：数据结构与算法课程设计院（系）：信息科学与技术学院专业班级：学号：姓名：指导老师：目录一 需求分析 31.1 问题描述： 31.2 功能要求： 3二 概要设计 3三 详细设计 33.1 数据类型定义 33.2 程序的主要函数 43.3 克鲁斯卡尔算法思想描述 43.4 克鲁斯卡尔算法设计 5四 测试分析 5五 心得体会 8附录：程序源代码 8一、 需求分析1.1 问题描述给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树， 并计算得到的最小生成树的代价。1.2 功能要求 城市间的距离网采用邻接矩阵表示，
2、邻接矩阵的存储结构定义采用课本中给出的定 义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在 屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的 代价。城市间的距离以邻接矩阵的方式输入（要求至少 6 个城市， 10条边）。 二、概要设计2.1 该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否 构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。2.2 该城市间的距离网用邻接矩阵表示。并且把 2 个城市的看成起点和终点，城市之 间的距离看成边，并以此设计结构体。定义结构体数组 ，将输入的矩阵转化为相对应的
3、 结构体来存储城市与城市直接的关系2.3先用judge（）判断能否生成是否为联通图，再用克鲁斯卡尔（Kruskal）算法将输 入的矩阵生立最小生成树，打印出来。创建用邻接矩阵表示的城市道路网输入城市数道路权值判断是否可以连通Krushal算法，并将所到的结果输出退出三、详细设计3.1 数据类型定义typedefstruct node /*构造一个结构体*/intstr; /*起点*/int end; /*终点*/int dis;/* 距离 */node;为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中 定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城
4、市的一维数组及int 型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对 应两个城市，这样就建立起了一个城市到城市之间的邻接矩阵。将该邻接矩阵转化为图 示的结构体，用于计算。3.2 程序的主要函数 能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历 城市生成最小生成树，通过计算得到最小生成树的代价主要函数：a) int menu ( )菜单函数，给用户提示信息，让用户选择相应功能。b) void create ( ) 输入城市信息函数，将用户输入的邻接矩阵以二维数组的形式存放到内存中，为 Krushal( )服务c) void judge (
5、)判断用户输入的邻接矩阵所转化的图是否可以生成最小生成树d) void find ( )判断当前是否构成回路的函数e) void Union ( )将能构成最小生成树的边添加到一个集合，f) void Krushal( )克鲁斯算法求最小生成树J屏0-ot克鲁斯卡尔算吐生成最小生成树的过程3.3 克鲁斯卡尔算法思想基本描述：假设连通图N= (V, E),则令最小生成树的初始状态为只有n顶点而无边的非连 通图T=(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依 附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一 条代价最小的边。以此类推，直至T
6、中所有顶点都在同一个连通分量上为止3.4 克鲁斯卡尔算法设计a. 设置计数器E,初值为0记录已选中的边数。将所有边从小到大排序，存于p 中。b. 从 p 中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若 是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c. 从E中删除此最小边，转b继续执行，直到k=n-1,算法结束d. 判断是否构成回路的方法：设置集合S，其中存放已加入到生成树中的边所连接 的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已 经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在 S 中，则不够成回
7、路。四、测试分析以一个6个城市、10条边的网络图为例进行测试196IS20193C11620112222189网络图邻接矩阵1 系统界面：兪构成最小生成树-.1 -成树 生成 小生 S 自3个最 信一成 Ki 间构帀 之霜 市否有 入断历出 12 3 4请输入所选功能丄-4求最小生成树2 输入信息请输入城市的T養如输入吕吟城市的邻接矩阵二1O0O0 16- 29X0000 100001610000 1 0000 G 52佯 11 luuuu 221119忑忑IS 丄 0000laaaa & 14 is 10000 9设置两顶点之间无边时x权值为100003 数据处理(1)、判断能否构成最小生成
8、树求最小生成树(2)、遍历所有城市生成最小生成数 F :e b u gn个减市连董的聂、生成顼Uxe 请输入所选功能4遍历所有城市得到最小生成树为；逼为11徑芻的代价为3 2 5E貝 二一到2 1 4#.市:V. V. V. V.-二-二-二一-二-t;二一 一 . nTK nTK nTK nTK nt-*- T 1 2 3 4 5 日第第第第霜3）、退出11n 啣#J片i旧 蜩 卩土丿J同尽v土丿J网網4逋出请输入所选功能直-44Ppess any key to continue五、体会心得通过本周的课程设计，终于圆满完成了课程设计的任务，我也有不少收获。既巩固 和加深了对数据结构的理解，认
9、识到数据结构是计算机专业一门重要的专业技术基 础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就 能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也 培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是 一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过 这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。参考文献1 .严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，20072 .谭浩强，张基温.C语言程序设计教程（第三版）北京：高等教育出版社，20063 .陈维新，林小茶
10、.C+面向对象程序设计教程.北京：清华大学出版社，20044 .苏仕华等.数据结构课程设计. 北京：机械工业出版社， 2005附录：程序源码#include #include #include #define max 20#define MAX_LNT 10typedefstruct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看 成一个边*/intstr; /*起点*/int end; /*终点*/int dis;/* 距离 */node;node pmax,temp;int pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX
11、_LNTMAX_LNT;/*n 表示城市个数，arcs记录城市间权值*/int menu( )/*菜单函数*/int m;printf(printf(nn);printf(printf(1输入城市之间的信息n);2判断是否能构成一个最小生成树n);printf(printf(printf(printf( scanf(%d,&m); return m;3 遍历所有城市生成最小生成树 n);4 退出 n);nn);请输入所选功能 1-4n);/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/* 初始化*/prex = x; rankx = 0;int
12、find(int x)/*找到这个点的祖先*/if(x != prex)prex = find(prex);return prex;void Union(intx,int y)/*将这两个添加到一个集合里去*/x = find(x);y = find(y);if(rankx = ranky)prey = x;rankx +;else prey = x;voidKruskal( )intans = 0,i,j,k = 0;/*ans 用来记录生成最小树的权总值*/int index;int count = 0;/*记录打印边的条数*/for(i = 1;i = n;i +)/*初始化数组 pre
13、x,rankx*/set(i);for(i = 1;i = n;i +)for(j = i + 1;j = n;j +)p+k.str = i;pk.end = j;pk.dis = arcsij; /*先把所有城市之间的路段看成一个边*/ for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/index=i;for(j=i+1;j=k;j+) if(pj.dis pindex.dis) index=j; temp=pindex;pindex=pi; pi=temp;for(i = 1;i = k;i +)if(find(pi.str) != find(pi.end)/*如果这两点连接在一起不构成一个回路, 则执行下面操作*/ printf(t 第 %d 条 路 段 为 ： %d-%d, 权 值 为 %dn,+ count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end);printf(t遍历所有城市得到最小生成树的代价为:dnn,ans);void create( )/*输入城市信息*/inti,j;printf(请输入城市的个数:n);scanf(%d,&n);printf(输入%d个城市的邻接矩
