《数据结构与算法》课程设计成果报告-最小生成树KRUSKAL算法.doc

河南工程学院数据结构与算法课程设计成果报告最小生成树KRUSKAL算法学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程-1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目KRUSKAL算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 算法分析与设计22.1 KRUSKAL算法定义22.2 存储结构设计32.1.1KRUSKAL算法并查集原理42.2.2 KRUSKAL算法路径压缩52.3 算法描述72.3.1 union类的描述72.3.2 kruskal类的描述82.4 程序流程图93 程序清单104 测试124.1 测试数据124.2 测试结果分析125 总结14参考文献151 课程设计目标与任务 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能选择图上任意一点做根结点，最小生成树输出采用顶点的集合和边的集合形式。1.1 课程设计目标依据最小生成树的思想掌握数据结构与算法的设计方法，提升自己对程序设计的认识，增强自己的综合素质。（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 （3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力。（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（5）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。1.2课程设计任务对给定的n定点连线的图，用Kruskal算法建立最小生成树，并得到最小生成树的代价。（1）对给定的图结构，用Kruskal算法基本思想求解出所有最小生成树；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3） 遍历图生成最小生成树，通过计算得到最小生成树的代价，从而能够更好运用Kruskal算法。（4）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。 2 算法分析与设计分析算法的实现过程，选用合适的数据结构,设计适合题目要求的算法。要确定图的存储形式，通过对题目的具体分析，发现问题主要操作是路径的输出，因此采用边集成路径设计和邻接矩阵比较方便以后的编程。根据课题设计要求，将整体程序设计分为四大模块，以下是四大模块的具体分析思路。2.1 KRUSKAL算法的定义假设连通网N=(V,E)是一个含有n个定点的联通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个致函n个顶点,而边集为空的子图，若将该子图中各个顶点看成是个棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集e中选取一条权值最小的边，若该条的两个顶点分属不同的树，则将其家入到子图，也就是说，将这俩个顶点分别所在的两棵树合成一棵树；反之，若将该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值的最小边再试之。以此类推，直到森里中只有一颗树，也即子图中含有n-1条边为止。 例如， 克鲁斯卡尔算法（Kruskals algorithm）是两个经典的最小生成树算法的较为简单理解的一个，这里面充分体现了贪心算法的精髓。大致流程可以用一个图来表示，这里的图选择了借用了Wikipedia上的那个，非常清晰且直观。 BC A如图2.1所示： 啊E DFG 图2.1克鲁斯卡尔算法5（a）（b）223234234（c）（d）（e）图2.1.1克鲁斯卡尔算法的描述例如，图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.1KRUSKAL算法的并查集的原理我们可以把每个连通分量看成一个集合，该集合包含了连通分量的所有点。而具体的连通方式无关紧要好比集合中的元素没有先后顺序之分，只有“属于”与“不属于”的区别。图的所有连通分量可以用若干个不相交的集合来表示。使用树来表示集合。树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表。如图2.2所示 ad b c 图2.2 并查集原理图树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示没有父节点。沿着每个节点的父节点指针不断向上查找，最终就可以找到该树的跟节点，即集合的代表元素。所以，并查集的初始化就是构造出一个森林，每个元素自身是一个集合。如图2.3所示： b a 图2.3 并查集的初始化2.2.2 KRUSKAL算法的路径压缩和所有树形结构一样，并查集也会发生退化，复杂度也随这退化而变得很高。如图2.3.1 1 2 74 图2.3.1 并查集退化为了防止退化的发生，可以通过记录每课树的高度，合并时总是从高度小的向高度大的连边。如下图：6 6 13 2 45 图2.4 路径压缩对于每个节点，一旦向上走到了一次跟节点，就把这个点到父亲的边改为直接连向根。而且，在此只上，在查询过程中向上查询经过的所有顶点，都可以改为直接连到根节点，这样再次查询这些节点时，就可以直接查询到根节点。如图2.5 ab c d 图2.5 路径压缩2优化后并查集的平均复杂度为(n)。2.3 KRUSKAL算法描述2.3.1 union类的描述表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，并获取下一条边继续判断，直到结束，否则舍弃该边。还剩下边？否按权排序与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-3 cost:2 1-2 cost:42-3 cost:1 2-5 cost:53-5 cost:64.2 测试结果分析 上述测试数据体现在代码中为： edge e=(1,3,2),(1,2,4)(3,2,1),(2,5,5),(3,5,6); kruskal test(5,4,e); couttest.solve()endl;所构成的图如图4.1所示5496871235132261928347106733图 4.1中红色的边构成最小生成树,总和为8。5 总结2014年即将结束2015年即将到来，我迎来这一学年的最后一次实践考验，通过这一周的学习和实践，不仅巩固了已学的知识，更学到了很多新的思想。使我体会到了灵活运用学过的知识解决