《最小生成树Kruskal算法报告》由会员分享，可在线阅读，更多相关《最小生成树Kruskal算法报告（26页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树Kruskal算法院（系）：计算机学院专业：计算机科学与技术目 录1课程设计介绍11.1课程设计内容11.2课程设计要求12课程设计原理22.1课设题目粗略分析22.2原理图介绍32.2.1功能模块图32.2.2流程图分析43数据结构分析103.1存储结构103.2算法描述104调试与分析134.1调试过程134.2程序执行过程13参考文献16附 录（关键部分程序清单） 171课程设计介绍1.1课程设计内容设计程序，编写算法能建立带权图，并能够用Kruskal算法求该图的最小 生成树，系统主要功能如下：1. 最小
2、生成树能够选择图上的任意一顶点做根结点；2. 最小生成树输出不必采用图形方式，可按父结点和子女结点集的形式 输出。1.2课程设计要求1. 顶点信息用字符串，数据可自行设定；2. 参考相应的资料，独立完成课程设计任务；3. 交规范课程设计报告和软件代码。2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为五大模块。此五个模块相互联系，有 嵌套调用的情况，以下是五个模块的大体分析：1. 创建模块，建立无向连通图，创建图的总信息；2. 发现模块，用Kruscal算法求最小生成树并调用search()函数；3. 寻找模块，找出最小边(路径)，使各连通分量相统一，输出最小生成树对应边及
3、对应结点并调用change()函数；4. 改变模块，改变两个结点间的权值，使下一次寻找时不至于重复；5. 选择模块，选择最小生成树的根结点并按父亲节点和子女结点的形式输出最小生成树。2.2原理图介绍2.2.1功能模块图最小生成树Kruskal算法发 现 模 块寻 找 模 块改变模块选择模块图2.1功能模块图2.2.2流程图分析1.创建模块，建立无向连通图，创建图的总信息，流程图如下:输入结点数和边数开始图2.2创建块流程图2.发现模块，用Kruscal算法求最小生成树并调用search()函数，流程图如下:图2.3发现模块流程图3.寻找模块，找出最小边(路径)，使各连通分量相统一，输出最小生成
4、树对 应边及对应结点并调用change()函数，具体流程图如下：图2.4寻找模块流程图N-Fathermin_sign!=(k*X)图2.5寻找模块流程图4.改变模块，改变两个结点间的权值，使下一次寻找时不至于重复，具体流程图如下:图2.6改变模块流程图5.选择模块，选择最小生成树的根结点并按父亲节点和子女结点的形式输出最小生成树法，具体流程图如下:图2.7选择模块流程图3数据结构分析3.1存储结构定义结构体数组建立整个图的信息，包括图的各个结点的名称及对应的数字 编号，连接两结点的边的权值，建立存在互相连通的两结点之间的联系且采用从 头插入的链表连接方式，并且每个结点建立对应的邻接表，都采用
5、头插入的方式， 相互连接的两结点都存有对应的边的权值，存储代码如下： typedef struct link (int connect;/结点编号int fee;/权值struct link *next;edgenode;typedef struct node(char name10;/结点名称edgenode *link;jiedian;typedef struct(jiedian vexMAXSIZE;int jiedian_n,jiedian_e;/结点个数，边数(路径数) jiedian_graph;3.2算法描述1. 建立两结点间联系，采用从头插入的方式，其中p,q分别为两项链结点的
6、编 号，简单算法说明如下：p-next=ga-vexa.link;/建立两个结点间的联系ga-vexa.link=p;q-next=ga-vexb.link;ga-vexb.link=q;2. 寻找所建图中最小权值所在边对应的两个结点，如果寻找过则重新标记为 一个统一的更大权值，以防止下次寻找时影响寻找的结果，简单算法说明 如下：for(j=1;jjiedian_n+1;j+)/ 找权值最少的两个结点p=ga-vexj.link;记下当前结点，以便在此结点的联系链中找到此链下的最小权值边(路径) while(p!=NULL)if(p-feefee!=100)min=p-fee;min_sign
7、=p-connect;min_record=j;p=p-next;3. 修改找到最小权值的边的权值，使其赋予更大的权值，简单算法说明如下:while(p!=NULL)if(p-connect=min_b)p-fee=100;q=p;p=p-next;4. 输出结点所连接的各个结点的的名称，运用啦信息表建立的头插入方式 的邻接表，简单算法说明如下：while(p!=NULL)if(Motherp-connect!=0)printf(%s ,ga-vexp-connect.name);Motherp-connect=0;p=p-next;4调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：
8、1. 邻接表的建立采用了头插入的方式，对应结点的插入顺序不应错误。2. 各个连通分量之间达到统一，此结果的实现采用了对不同连通分量所对 应的结点运用不同的但有一定规律的数字进行标记，各种情况下标记数 的是否相同代表着不同的情况，进行结果不同的处理。3. 对所见图中最小权值的寻找，运用了对寻找过得边的权值进行重新赋予 新的统一的更大的权值，以避免此后再次寻找对结果的干扰。4. 输出结点所连接的各个结点的的名称，按照父亲结点子女结点的方式输 出，运用啦信息表建立的头插入方式的邻接表。程序执行过程*欢迎进入最小生成树Kruskal算法*1. 进入最小生成树算法系统，选择相应的数字以进入对应模块，执行
9、结果如下:k x X X X X X欢 i 印 i井入最 / |、牛成揪KrtW La 1 算法卜建立图的信息2 =找出最小三成树及所对应边 加选择根结点显号信羸入1-4选项图4.1进入系统2. 连通图的建立，输入各个结点的信息和边的信息输入和执行结果如下:个(IU1417292538 eerr号号号号号 ,UE ;.nE :.-nw.-CL 14411114.习4.FrTrT占5接世个奖个据个费个盘个 结连第第第第第蜀厚里景两 AAAAAAAAAAAAAAAA青青青青M.S.S星后青青青青青青青青图4.2输入信息3. 输出路径及对应结点名和权值，计算出总的权值，具体操作结果如下:片建立图的信
10、息和找出最小生成树及所对应辿 加选择根结点缉号 如输入I选项2以下是路径点名-结点名-权值qqvjvj4wwee5京权值=9图4.3输出信息4. 选择根结点并根据根结点按照父亲结点子女结点的形式输出图中的结点具体 操作结果如下：4建立图的信息2 =找出最小与成树及所对应边 新选择根结点苦号4很中请输乳-4选项输入根结点编号：3根结点为:ee以下是最小生成树结点根结点为父亲结点, 父亲结点名一一子女结点名，perr ww qq图4.4输出结果5. 选择退出选项，推车系统，操作结果如下:片建豆图的佰息2 =找出最小与成树及所对应边和选择根结点蕴号退出信蜀入H-4选顶图4.5选择信息参考文献1 严蔚
11、敏，吴伟民.数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟C程序设计M.北京：高等教育出版社，2004.3 谭浩强.C程序设计M.北京：清华大学出版社，2005.4 殷人昆等.数据结构（用面向对象方法与C+描述）.清华大学出版，2005.5 宁正元等.算法与数据结构习题精解和实验指导.清华大学出版社，2007.录（关键部分程序清单）程序代码#include#include#include#include #define MAXSIZE 100#define X 33#define Y 10typedef struct linkint connect;/ 结点编号int fee;/
12、 权值struct link *next;edgenode;typedef struct nodechar name10;/ 结点名称edgenode *link;jiedian;typedef structjiedian vexMAXSIZE;int jiedian_n,jiedian_e;/ 结点个数，边数（路径数） jiedian_graph;jiedian_graph ga;int total_fee=0;/记录总费用int menu（）int a;int b=0;printf（1:建立图的信息n）;printf（2:找出最小生成树及所对应边n）;printf（3:选择根结点编号n）;printf（4 :退出 n）;printf（请输入 1-4 选项n）;doscanf(%d”,&a);if(a0&ajiedian_n)
