数据结构课程设计报告-- KRUSKAL算法实现.doc

河南工程学院数据结构与算法课程设计成果报告KRUSKAL算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目KRUSKAL算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述22.4 程序流程图23 程序清单34 测试44.1 测试数据44.2 测试结果分析45 总结5参考文献7附 录81 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。2 分析与设计2.1 题目需求分析要求：（1）对给定的图结构，用KRUSKAL算法基本思想求解出所有最小生成树；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。分析：Dijkstra算法即解决单源最短路径问题，单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。如果P(i,j)=Vi.Vk.Vs.Vj是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。2.2 存储结构设计 Dijkstra算法中使用较为普遍的堆数据结构有二叉堆、二项堆和Fibonacci堆。其中二叉堆在内存中被存储为经过特殊排列的完全二叉树。二叉堆具有以下操作特性： 1）其获取最小节点的操作Get_Min时间复杂度为(1)O，总计算机指令一条； 2) 将一个新的元素插入堆中的操作Insert时间复杂度为(log)On，总指令最坏情况下要3*log1n+条； 其插入操作可以通过以下三步来执行： 将新元素插入到堆的末尾，计算机指令一条； 将新元素与其父节点比较，如果新元素比其父节点小则交换它与其父节点，计算机指令三条； 重复执行第二步直到新元素被提升到树根或不比其父节点小。 3）其从堆中去除最小节点的操作Extract_Min操作时间复杂度为(log)On，最坏情况下需要3*log2n+条指令； 根据二叉堆的特点，为了实现剔除最小节点的操作，只需要进行以下四步操作： 将其根节点从树中剔除，一条指令； 将树中的最后一个子孙节点放在树根位置，一条指令； 将新的树根与其子节点依次比较，如果大于其子节点就于该子节点交换，三条； 重复执行第三步，直到新根元素被交换到底或不比其任何一个子节点大。 4）降低堆中某一元素值的同时也要对该元素进行重新定位排序。由于是小顶堆，所以需要将被降低值的元素执行向根节点方向的比较操作，因此其时间复杂度最坏情况下也为(log)On，最坏需要3*logn条指令。 Fibonacci堆和二项堆的原理十分相似，且Fibonacci堆是缘于二项堆的灵感而创建的，但在时间复杂度上又优于二项堆，因此我们这里只讨论Fibonacci堆。Fibonacci堆是Fredman和Tarjan 于1984年发明的，它是对优先队列一个很好的实现3。它的目的是在计算最小生成树根最短路径的过程中将操作步数最小化。因此我们感兴趣的操作有插入，减小键值，合并和删除最小键值节点(合并操作的重要性将在我们叙述Fibonacci堆操作的过程中阐述)。而Fibonacci堆通过一种“懒惰”行为来实现这一目的，即“在不得不做的时候再做”，这样会使以后的工作更加简单。 Fibonacci堆H是一些堆排序树的集合，它具有以下几个特点： 1）这些树的根用一个双向链表存储起来(成为H的根表)； 2）每棵树的根节点为树中权值最小的节点(遵循了堆排序树的特点)； 3）我们通过一个指向全局最小的树根来访问堆； 4）对于每个节点x，我们储存x的阶(也称为度数)，它代表了节点x的孩子节点数目；另外还有一个mark，是一个布尔值。 5）对于每个节点，我们最多有四个指针分别指向该节点的父节点，其中的一个子节点，和一左一右两个兄弟节点，兄弟节点之间通过一个双向循环链表连接起来。 Fibonacci堆具以下7个常用操作： 1）合并树：设x和y分别是堆上两棵树的根节点，由于堆的性质：树的根节点值最小，所以只需要比较x和y的值，如果xy则将x作为y的一棵子树，由此可知该操作的时间复杂度为(1)O； 2）插入新元素：将欲插入元素x作为一棵根树直接插入到堆的根表中，并与根表中原最小的根比较确定最小根，由此可知其时间复杂度也为(1)O； 3）剪枝操作：若x不是一棵树的根节点，将x作为根的子树从其父节点剪下放到根表中，并与原根表比较确定新的最小根，时间复杂度为(1)O； 4）减小节点值操作：欲减小x节点的值只需要将x进行剪枝后更新x的值，时间复杂度为(1)O； 5）删除最小的节点：我们知道根表中保存了最小节点的指针，因此只需将最小根树的根节点删除，并将其子树放到根表中，并搜索整个根表确定新的最小根，时间复杂度为Om，其中m是根表中根的个数； 6）标记节点：当且仅当节点x不是根且失去了一个孩子的时候我们标记x的mark为真，当x变为根时去除标记；当节点x被标记时不能失去另一个孩子； 7）合并相同度数的节点：为了确保每个节点的后代数目不会过多，我们需要对具有相同度数的根节点进行合并树操作，并且该操作在插入、剪枝和删除最小节点操作后一定会进行； 通过对两种数据结构的详细探讨我们可以看出：虽然Fibonacci堆在插入和减小节点值操作上的直接时间复杂度要优于二叉堆，但是Fibonacci堆为了实现其“懒惰”的目的进行了很多步小开销的操作来复杂化数据结构。这增大了删除最小节点的时间复杂度（因为其不但要进行基本的操作，之后还必须跟随合并和标记操作），并且显然Fibonacci堆的计算机指令要远远多于二叉堆。经研究在GIS等的交通网络等稀疏图中Fibonacci堆并不能发挥其优越性。 配对堆的思想来源于Fibonacci堆，但却比Fibonacci堆要简单，性能也稍有改进。配对堆数据结构除了具有根节点是最小原素的基本堆性质外还具有如下性质： 1）每个堆节点除了保存基本元素外，还保存了三个指针，分别指向该节点的前驱节点、左儿子节点和右兄弟节点； 2）如果节点n是某个节点的最左儿子，则其前驱节点指针指向其父节点，否则应指向其左兄弟节点； 3）任何一个节点的值均小于等于其最左儿子节点； 4）同一层次串联的兄弟节点没有大小顺序，但均大于其最左兄弟节点的父节点。 配对堆主要有4种基本操作： 1）合并子堆：设X与Y分别是两个子配对堆的根节点，如果XY则令X堆成为Y的最左子堆，反之则令Y成为X的最左子堆，时间复杂度()1O，需要五条计算机指令（对比、修改X的最左儿子指针、修改Y的前驱和右兄弟指针、修改Y右兄弟的前驱指针）； 2）插入节点：首先令插入的节点为一个单节点子堆，然后将其与欲插入堆进行合并操作，时间复杂度()1O，需要五条计算机指令； 3）降低节点值：首先将欲降低的节点及其子孙从堆中剔除，降低元素的值，然后将降低根节点值后的堆与原堆进行合并操作，时间复杂度(1)O，需要10条指令； 4）删除最小节点：将堆的根节点删除，然后将剩余的根的直接子节点作为根，分成M个子堆，然后所有的子堆合并在一起。该操作的时间复杂度为()Om，需要27*m+条指令。 通过以上分析我们可以得出两个结论： 1）堆数据结构是比较适合Dijkstra算法操作特点的数据存储解决方案； 2）从时间复杂度上直观的看，配对堆要优于二叉堆； 3）在计算实现过程中，配对堆需要7*12m+条计算机指令（m是根的直接儿子节点数）而二叉堆一次运行需要9*log4n+条指令（n是节点总数）。 4) 无论是二叉堆还是配对堆，对于在堆中查找搜索已知节点都没有很好的解决，只能使用遍历搜索。2.3 算法描述如果存在一条从i到j的最短路径(Vi.Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi.Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离distj=mindistj,disti+matrixij。根据这种思路，假设存在G=，源顶点为V0，U=V0,disti记录V0到i的最短距离，pathi记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使disti值最小的顶点i，将i加入到U中；2.更新与i直接相邻顶点的dist值。(distj=mindistj,disti+matrixij)3.知道U=V，停止。2.4 程序流程图 图2.1 KRUSKAL算法流程图3 程序清单*Dijkstra求单源最短路径 2010.8.26*/ #include #include#define M 100#define N 100using namespace std;typedef struct node int matrixNM; /邻接矩阵 int n; /顶点数 int e; /边数 MGraph; void DijkstraPath(MGraph g,int *dist,int *path,int v0) /v0表示源顶点 int i,j,k; bool *visited=(bool *)malloc(sizeof(bool)*g.n); for(i=0;i0&i!=v0) disti=g.matrixv0i; pathi=v0; /path记录最短路径上从v0到i的前一个顶点 else disti=INT_MAX; /若i不与v0直接相邻，则权值置为无穷大 pathi=-1; visitedi=false; pathv0=v0; distv0=0; visitedv0=true; for(i=1;ig.n;i+) /循环扩展n-1次 int min=INT_MAX; int u; for(j=0;jg.n;j+) /寻找未被扩展的权值最小的顶点 if(visitedj=false&distjmin) min=distj; u=j; visitedu=true; for(k=0;k0&min+g.matrixukdistk) distk=min+g.matrixuk; pathk=u; void showPath(int *path,int v,int v0) /打印最短路径上的各个顶点 stack s; int u=v; while(v!=v0) s.push(v); v=pathv; s.push(v); while(!s.empty() couts.top()ne&e!=0) int i,j; int s,t,w; /表示存在一条边s-t,权值为w MGraph g; int v0; int *dist=(int *)malloc(sizeof(int)*n); int *path=(int *)malloc(sizeof(int)*n); for(i=0;iN;i+) for(j=0;jM;j+) g.matrixij=0; g.n=n; g.e=e; for(i=0;istw; g.matrixst=w; cinv0; /输入源顶点 DijkstraPath(g,dist,path,v0); for(i=0;in;i+) if(i!=v0) showPath(path,i,v0); coutdistiendl; return 0;4 测试4.1 测试数据测试数据：