《数据结构与算法》课程设计成果报告-KRUSKAL算法实现.doc

河南工程学院数据结构与算法课程设计成果报告KRUSKAL算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程-1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目KRUSKAL算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 KRUSKAL算法概述22.2 存储结构设计32.1.1并查集的实现原理32.2.2 路径压缩42.3 算法描述62.3.1 union_search_set类的设计62.3.2 kruskal类的设计72.4 程序流程图83 程序清单94 测试114.1 测试数据114.2 测试结果分析125 总结13参考文献141 课程设计目标与任务1.1 课程设计目标（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 （3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力，增强理论与实践相结合的技巧。（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（5）增强团队合作意识，初步了解软件开发的一般过程，培养学习热情以及加强自主学习。（6）训练自己动手分析，解决问题的能力，掌握调试程序，排成错误的常用技巧。（7）增强动手能力，学会结合实际解决问题。1.2 课程设计任务（1）对给定的图结构，编写程序用KRUSKAL算法基本思想求解出所有最小生成树；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所编写的程序来实现相关问题的求解。2 分析与设计分析算法的实现过程，选用合适的数据结构,设计适合题目要求的算法。2.1 KRUSKAL算法概述假设连通网N=(V,E),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。在中选择代价最小的边，若该边依附的顶点落在中不同的连通分量上，则将此边加入到中，否则舍去此边而选择下一条代价最小的边。依次类推，直至中的所有顶点都在同一连通分量上为止。5（a）（b）223234234（c）（d）（e）图.1 kruskal过程描述例如，图2.1所示为依照库鲁斯卡尔算法构造一棵最小生成树的过程。（a）代价分别为1，2，3，4的4条边由于满足上述条件，则先后被加入到中，代价为5的两条边（v1,v4)和（v3,v4)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入中，则会使中产生回路，而下一条代价(=5)最小的边(v2,v3)联接两个连通分量，则可加入，由此，构造成一棵最小生成树。上述算法至多对e条边各扫描一次，若采用快速排序来保证每次都选择最小的边，排序的时间复杂度为(eloge)。由此，克鲁斯卡尔算法的时间复杂度为O(eloge)。2.2 存储结构设计在选择边加入连通网时，应保证插入的边所依附的两个顶点没有在一个连通分量上。因为并查集可以高效地判断两集合是否相交，故选择并查集作为该算法的数据结构。每个集合可能包含一个或多个元素，并选出一个元素作为该集合的代表。给定一个元素，并查集可以迅速找到该元素所在集合的代表，从而通过判断两个元素的代表是否相同来判断两者是否在同一个集合中。表.1 并查集的基本基本操作并查集的基本操作见表2.1函数名功能union_search_set(n)初始化一个含有n个元素的并查集same(x,y)判断元素x,y是否位于同一集合unite(x,y)把元素x和y所在的集合合并2.1.1并查集的实现原理使用树来表示集合。树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表。如图2.2所示a b d c e f g图.2并查集的树表示树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示没有父节点。沿着每个节点的父节点指针不断向上查找，最终就可以找到该树的跟节点，即集合的代表元素。所以，并查集的初始化就是构造出一个森林，每个元素自身是一个集合。如图2.3所示： b c e d a图.2 并查集的初始化2.2.2 路径压缩和所有树形结构一样，并查集也会发生退化，复杂度也随这退化而变得很高。使得并查集的查询效率大大下降，如图2.3图2.3 并查集的退化 2 7 4 1这时，每查询一个值，都需要遍历整棵树才能找到集合的代表元素，使得使用并查集的意义不大。尤其在需要多次查询的情况下，退化使每次查询做了大量的重复工作，浪费了大量的时间。为了防止退化的发生，可以通过记录每课树的高度，合并时总是从高度小的向高度大的连边。如下图：图2.4 路径压缩对于每个节点，一旦向上走到了一次跟节点，就把这个点到父亲的边改为直接连向根。而且，在此只上，在查询过程中向上查询经过的所有顶点，都可以改为直接连到根节点，这样再次查询这些节点时，就可以直接查询到根节点。如图2.5图.5 路径压缩优化后并查集的平均复杂度为(n)。2.3 算法描述分别设计union_search_set类实现并查集和kruskal类实现KRUSKAL算法求最小生成树。2.3.1 union_search_set类的设计表2.1 union_search_set类的成员函数union_search_set类的成员函数及其功能如表2.2所示成员函数名称接受参数返回值类型功能描述union_search_set初始化元素个数void初始化并查集find集合中一个元素int查找该元素的根节点unite两个不同集合的元素void将两个元素所在集合合并same集合中一个元素bool判断两个元素是否位于同一集合中在union_search_set类中用编号代表每个元素。数组par表示的是父亲的编号，当parx=x时，x是所在的树的根。所以，应将par中的所以元素初始化为其下标。而find也只需不断向上查找，直到parx=x。代码如下：int find(int x)if (parx= x) return x; else return parx = find(parx);same函数只要调用find函数判断两个元素的根节点是否相同即可。代码:bool same(int x, int y)return find(x) = find(y);unite函数通过rank数组记录树的高度，根据高度决定连边的方式，防止并查集发生退化，代码如下：void unite(int x, int y) x = find(x); y = find(y); if (x = y) return; if (rankx ranky) parx = y; else pary = x; if (rankx = ranky) rankx+;2.3.2 kruskal类的设计kruskal类实现了kruskal算法求最小生成树。通过union_search_set类中实现的并查集判断是否成连通图。并调用std:sort()对权值排序，每次都选取权值最小的边，同时调用union_search_set类判断当前边是否与T成环，若成环，则舍去该边，继续判断下一条，否则将该边加入T。solve代码：int solve(void)int res=0; union_search_set uset(V); std:sort(es, es + E, kruskal:cmp); for (int i = 0; i E; i+) edge e = esi; if (!uset.same(e.v, e.u) uset.unite(e.v, e.u); res += e.cost; return res;2.4 程序流程图程序以kruskal类实现求最小生成树。构造函数接受3个参数，分别是顶点数，边数，和表示边的结构体数组(edge)。同时初始化并查集，并将边按权升序排序，依次取权最小的边判断是否与T连通，如果连通，则加入T，并获取下一条边继续判断，直到结束，否则舍弃该边。流程图如图2.6所示还剩下边？否按权排序与T成环?权最小的边舍去加入T结束是否是开始图2.6 程序流程图3 程序清单/=/ Name : KRUSKAL.cpp/ Author : frank/ Version :/ Copyright : Your copyright notice/ Description : KRUSKAL in C+, Ansi-style/=#include #include#includeusing namespace std;class union_search_set/并查集private: int *par ; int *rank ;public: union_search_set(int n) /元素个数 par = new intn + 1; rank = new intn + 1; for (int i = 0; i n; i+) pari = i; ranki = 0; int find(int x) if (parx= x) return x; else return parx = find(parx); void unite(int x, int y) x = find(x); y = find(y); if (x = y) return; if (rankx ranky) parx = y; else pary = x; if (rankx = ranky) rankx+; bool same(int x, int y) return find(x) = find(y); ;struct edge/边 int u; int v; int cost; edge(void):u(0),v(0),cost(0); edge(int x,int y,int z):u( x),v( y),cost( z);class kruskalprivate: static bool cmp(const edge& e1, const edge& e2)/sort比较函数 return e1.cost e2.cost; int V, E; edge *es = NULL;public: kruskal(int v, int e, edge* tes)/V:顶点数 E:边数 V = v; E = e; es = tes; int solve(void) int res=0; union_search_set uset(V); std:sort(es, es + E, kruskal:cmp); for (int i = 0; i y cost:z在图中表示节点x与y间有一条边，权值为z1-2cost:5 2-3cost:1 2-5cost:3 3-5cost:2 1-7cost:2 4-7cost:34-5cost:68-9cost:1 7-9cost:9 6-9cost:2 3-9cost:8 7-6cost:3 8-7cost:43-6cost:7 5-7cost:10 1-4cost:6 1-3cost:7 5-8cost:3 9-10cost:5 8-10cost:35-7cost:10其中，顶点数为10，边数为20。将上述数据根据约定的规则传递给kruskal类，并调用kruskal:：solve()成员函数计算结果，由主程序输出至控制台。程序计算后返回求得的最小生成树的各边权值总和。4.2 测试结果分析 上述测试数据体现在代码中为： edge e=(1,2,5),(2,3,1),(2,5,3),(3,5,2),(1,7,2),(4,7,3),(4,5,6),(8,9,1),(7,9,9),(6,9,2),(3,9,8),(7,6,3),(8,7,4),(3,6,7),(5,7,10),(1,4,6),(1,3,7),(5,8,3),(9,10,5),(8,10,3),(5,7,10); kruskal test(10,20,e); couttest.solve()endl;所构成的图如图4.1所示3549687123513226192834710673 10537图4.1 测试数据表示图中以圆形表示节点，其中写的数字为节点编号，每条边上的数字为该边的权值。所有的边在程序中以结构体数组的方式储存，并作为参数传递给kruskal类，最终由其成员函数solve()计算出结果并返回。该测试数据程序根据克鲁斯卡尔算法求得的结果为20。5 总结通过这一周的学习和实践，不仅巩固了已学的知识，更学到了很多新的思想。使我体会到了灵活运用学过的知识解决实际问题，理解了选择合适的数据结构解决问题的重要性。克鲁思卡尔算法的实现，使我学到了解决一个问题的基本方法：从分析问题，选取数据结构，设计算法，编码实现，每一个过程都对程序设计的思想巩固的过程。对并查集的原理有了更深刻的理解，尤其是自己编码实现了对并查集的路径压缩，防止树型结构的退化，使并查集查询的复杂度大大降低。最后，也认识到了自己还有很多知识掌握的不够牢固，只有在不断的尝试中积累经验，使自己学到更多的知识。参考文献1 秋叶拓哉等.挑战程序设计竞赛（第2版）. 人民邮电出版社2 严蔚敏等.数据结构（C语言版）.清华大学出版社3 Thomas H.Cormen.算法导论（第二版）. 机械工业出版社出版4 Jon Bentley.编程珠玑. 人民邮电出版社/=/ Name : KRUSKAL.cpp/ Author : frank/ Version :/ Copyright : Your copyright notice/ Description : KRUSKAL in C+, Ansi-style/=#include #include#includeusing namespace std;class union_search_set/并查集private: int *par ; int *rank ;public: union_search_set(int n) /元素个数 par = new intn + 1; rank = new intn + 1; for (int i = 0; i n; i+) pari = i; ranki = 0; int find(int x) if (parx= x) return x; else return parx = find(parx); void unite(int