《acm图论一学习教程.pptx》由会员分享，可在线阅读，更多相关《acm图论一学习教程.pptx（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论基础图论基础并查集及其应用并查集及其应用最小生成树：最小生成树：Kruskal Kruskal算法，算法，PrimPrim算法算法最短路径：最短路径：DijkstraDijkstra算法，算法，FloyedFloyed算法，算法，Bellman-FordBellman-Ford算法算法EulerEuler回路，回路，HamiltonHamilton回路回路二分图的最大匹配二分图的最大匹配第1页/共87页学习图论的误区学习图论的误区1 1 模板模板只知道每种算法的模板，不深究其中的方法。只知道每种算法的模板，不深究其中的方法。这样平时做题这样平时做题时可以做的省事，但是在比赛时就会觉得这个题
2、是用这个模板但发时可以做的省事，但是在比赛时就会觉得这个题是用这个模板但发现不了陷阱一直现不了陷阱一直WAWA。例如最大匹配。例如最大匹配-最小覆盖原则，如果只知道最大最小覆盖原则，如果只知道最大匹配算法模板，遇到一个最小覆盖的问题就不会做了，实际上这两匹配算法模板，遇到一个最小覆盖的问题就不会做了，实际上这两个问题是等价的。如果连定义都说不明白的话，会显得你很个问题是等价的。如果连定义都说不明白的话，会显得你很lowlow。2 2 递归与非递归递归与非递归图论有很多算法可以用递归实现。例如匈牙利算法，递归与非图论有很多算法可以用递归实现。例如匈牙利算法，递归与非递归实现都能解决最大匹配问题，
3、而且递归可读性与条例性更强。递归实现都能解决最大匹配问题，而且递归可读性与条例性更强。但在顶点数量很大时，非递归算法就能体现出他的优势：无须担心但在顶点数量很大时，非递归算法就能体现出他的优势：无须担心栈溢出。所以希望，学有余力的同学能够了解一下你所掌握的算法栈溢出。所以希望，学有余力的同学能够了解一下你所掌握的算法的非递归实现。的非递归实现。3 3 彻底明白算法后，每次也只是直接复制代码彻底明白算法后，每次也只是直接复制代码 这样的结果就是：忘的非常快。非常快。快。这样的结果就是：忘的非常快。非常快。快。每次敲代码都是对算法的重新复习，甚至可以重新审视自己的算法每次敲代码都是对算法的重新复习
4、，甚至可以重新审视自己的算法实现，从而优化自己的代码。记得耀哥就敲过这些算法做消遣，而实现，从而优化自己的代码。记得耀哥就敲过这些算法做消遣，而不是玩扫雷。不是玩扫雷。第2页/共87页并查集第3页/共87页并查集引例：亲戚(relatives)问题或许你并不知道，你的某个朋友是你的亲戚。他可能是你的或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！曾祖父的外公的女婿的外甥女的表姐的孙子！如果能得到完整的家谱，如果能得到完整的家谱，判断两个人是否亲戚判断两个人是否亲戚应该是可行的应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家，但如果两个
5、人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。况下，最好的帮手就是计算机。第4页/共87页并查集为了将问题简化，你将得到一些亲戚关系的信息，如为了将问题简化，你将得到一些亲戚关系的信息，如MarryMarry和和TomTom是亲戚，是亲戚，TomTom和和BenBen是亲戚，等等。从这些信息中，你是亲戚，等等。从这些信息中，你可以推出可以推出MarryMarry和和BenBen是亲戚。是亲戚。请写一个程序，对于有关亲戚关系的提问，以最快的速度给请写一个程序，对于有关亲戚
6、关系的提问，以最快的速度给出答案。出答案。第5页/共87页并查集Input:Input:n 第 一 部 分 以 N N，M M开 始。N N为 问 题 涉 及 的 人 的 个 数(1(1 N N 20000)20000)。这些人的编号为1,2,3,1,2,3,N N。下面有M M行(1(1 M M 1 1 000 000)000 000)，每行有两个数a ai i,b,bi i，表示已知a ai i和b bi i是亲戚。n 第二部分以Q Q开始。以下Q Q行有Q Q个询问(1(1 Q Q 1 1 000 000 000)000)，每行为c ci i,d,di i，表示询问c ci i和d di
7、 i是否为亲戚。n输出：n 对于每个询问c ci i,d di i，输出一行：若c ci i和d di i为亲戚，则输出“YesYes”，否则输出“NoNo”。第6页/共87页并查集n输入样例：n10 710 7n2 42 4n5 75 7n1 31 3n8 98 9n1 21 2n5 65 6n2 32 3n3 3n3 43 4n7 107 10n8 98 9输出样例：输出样例：YesYesNoNoYesYes 第7页/共87页问题分析 我们可以将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。很自然地就得到了一个有N个顶点M条边的图论模型，注意到传递关系，在此
8、无向图中的一个连通分支中的任意点之间都是亲戚。对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通分支中。第8页/共87页问题分析 这样的解题思路很清楚，对于输入的N个点M条边，建立一个无向图（保存边），找出所有的连通块（遍历算法），然后根据提问逐个进行判断。但是本题的数据范围很大，1 N 20000,1 M 1 000 000，不管是从空间上看还是从时间上看，都很难接受。第9页/共87页问题分析 再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：第一行是N，M。N为问题涉及的人的个数，下面有M行，每行有三个数ki,ai,b，其含义如下：ai和bi表示两个元素，k
9、i为0或1ki为1时，表示这是一条边的信息，即表示ai和bi是亲戚关系ki为0时，表示这是一个提问，要你根据此行以前所得到的信息，判断ai和bi是否是亲戚，对于每条提问回答Yes或No。第10页/共87页问题分析 这个问题比原问题更复杂些(复杂在何处?)，需要在任何时候回答提问的两个人的关系，是一种动态判断。并且对于信息提示还要能立即合并两个连通分支。采用连通图思想在实现上就有点困难，因为要实时地表示人与人之间的关系。第11页/共87页问题分析 可以用集合的思路来考虑这个问题(从逻辑上来看，这的确是个集合问题)：对每个人都建立一个集合；开始的时候，集合元素是这个人本身，表示开始时不知道任何人是
10、他的亲戚；以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中，看两个元素是否属于同一集合。第12页/共87页输入关系输入关系 分离集合分离集合初始状态初始状态 1234567891012345678910(2,4)12,435678910(2,4)12,435678910(5,7)12,435,768910(5,7)12,435,768910(1,3)(1,3)1,32,45,768910 1,32,45,768910(8,9)1,32,45,768,910(8,9)1,32,45,768,910(1,2)1,2,3,45,7
11、68,910(1,2)1,2,3,45,768,910(5,6)1,2,3,45,6,78,910(5,6)1,2,3,45,6,78,910(2,3)1,2,3,45,6,78,910(2,3)1,2,3,45,6,78,910第13页/共87页 由由上上图图可可以以看看出出，操操作作是是在在集集合合的的基基础础上上进进行行的的，在在操操作作过过程程中中，我我们们没没有有保保存存任任何何一一条条边边，而而且且每每一一步步得得到到的的划划分分方方式式是是动动态态的的。(为为什什么么可可以以采采用用集集合合？用用集集合合还还有有什什么么问问题题？)如如何何来来实实现现以以上上的的算算法法思思想想
12、呢呢？这这就就用到了用到了并查集并查集这种数据结构。这种数据结构。并查集的基本思想第14页/共87页并查集的基本思想什么叫并查集？并查集（union-find set）是一种用于分离集合(disjoint-set)的操作算法。学习一种新算法需要了解哪些方面？（特性/本质、存储表示/实现、操作、应用)。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系。第15页/共87页并查集的基本思想当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素(如a和b)所在的集合，然后才能合并。“并”、“查”和“集”三字由此而来。第16页/
13、共87页并查集的基本思想在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。并查集支持查找一个元素所属的集合，以及将两个元素各自所属的集合进行合并等操作。第17页/共87页并查集支持的操作动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现一般需要支持如下操作：MAKE-SET（x）建立一个新的集合 UNION（x,y）将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。FIND-SET（x）返回一个包含x的集合的代表。第18页/共87页并查集的实现及优化并查集的数据结构实
14、现方法很多，一般用的比较多的是数组实现、链表实现和树实现。第19页/共87页并查集的数组实现 用数组si记录元素 i 所属集合的编号。各操作的实现如下：MAKE-SET（x）：初始化只需做 si:=i;FIND-SET（x）：查找元素所属的集合时，只需读出si，时间复杂度为O(1)。UNION（x,y）：合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的 编号值，时间复杂度为O(n)。第20页/共87页并查集的数组实现实现简单，实际使用较多，但合并的代价太大。（diaosi用）。在最坏情况下，所有集合合并成一个集合的总代价会达到O(n2)（Wh
15、y?）。第21页/共87页并查集的数组实现 输入样例：输入样例：10 710 72 42 45 75 71 31 38 98 91 21 25 65 62 32 33 33 43 47 107 108 98 9UNIONUNION（x,yx,y）过程演示：）过程演示：12345678910S S1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 1011115558810S S1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10第22页/共87页并查集的链表实现每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类
16、，另有一个指针指向它的下一个元素。同时，为了方便实现，再设一个指针last表示链表中的最后一个元素（表尾）。第23页/共87页并查集的链表实现此时，各并查集操作的实现如下：MAKE-SET(x)：Sx.head:=x;Sx.next :=0;FIND-SET（x）：return Sx.head 两个过程的时间复杂度都为O(1)。第24页/共87页并查集的链表实现UNION(x,y)：假设UNION(x,y)的参数是有序的，即把y属于的集合合并到x的集合上去，有两种实现方法：（1）简单实现（2）快速实现 第25页/共87页UNION(x,y)操作的简单实现不考虑任何因素，出现FIND-SET（x
17、）FIND-SET（y）时，直接将y的表头接到x的表尾，同时将y所在集合中所有元素的head值设为FIND-SET(x)。同时x的表尾也应该设为原y表的表尾。注意：last指针其实只要在表头结点中记录即可，因为每一次查到FIND-SET（x）都可以得到表头元素。而链表中其他元素重新记录last是无意义的。第26页/共87页UNION(x,y)操作的简单实现我们总是把y接到x里去，那么如果y所在的集合非常大，每次赋值的代价就会非常高，考虑输入数据的特殊性，比如出现输入为：（2，1），（3，1），（4，1），（5，1），（6，1），(n,1)最坏情况下时间复杂度为O(n2)。第27页/共87页UN
18、ION(x,y)操作的快速实现上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但代价肯定不比原来差。这就是快速实现的思路。第28页/共87页UNION(x,y)操作的快速实现可以在node里多设一个域number，用来记录此条链表中成员的个数。显然number记录在表头元素中即可，将两表合并的时候，只要将表的number相加，因此维护起来是非常方便的。这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的number。第29页/共87页UNION(x,y)操作的快
19、速实现当有n个元素时，可以证明这种方法的效率在UNION上的花费（即重新赋值的次数）的上界是O(nlog2n)：考虑一个固定的对象x，当x的代表指针（head）被更新时，x必是属于一个较小的集合，因此，x的代表指针第一次更新后，结果集合必然至少有2个元素。第30页/共87页UNION(x,y)操作的快速实现u类似地，下一次更新后，x所在的集合至少有4个元素。u继续下去，可以发现，x的代表指针最多被更新log2n次，因为当x所在集合元素已经等于n以后，不可能再发生UNION操作。u所以，总共有n个元素时，操作的总次数不超过nlog2n次。这就保证了整个算法的复杂度是理想的。第31页/共87页 并
20、查集的链表实现是一种非常容易接受的算法，并且它并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实，它的思路和数组完全一样，的效率也是令人满意的。其实，它的思路和数组完全一样，所以实际使用较少。所以实际使用较少。合并两个集合时的实现过程如下：合并两个集合时的实现过程如下：UNION(x,y)UNION(x,y)x=FIND-SET(x);x=FIND-SET(x);y=FIND-SET(y);y=FIND-SET(y);if x.number y.number then UNION(x,y)if x.number y.number then UNION(x,y)else
21、UNION(y,x);else UNION(y,x);第32页/共87页并查集的树实现（重要）我们用有根树来表示集合，树中的每个结点包含集合的一个成员，每棵树表示一个集合。多个集合形成森林，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点的父结点指向根结点。第33页/共87页 下图表示了这种关系，它包含两个集合，即下图表示了这种关系，它包含两个集合，即b,c,e,hb,c,e,h和和d,f,gd,f,g，它们分别以，它们分别以c c和和f f作为代表：作为代表：第34页/共87页并查集的树实现 这种树结构也可以简单地用静态数组实现，设px表示元素 x 所指向的父亲。M
22、AKE-SET(x)：px=x;FIND-SET(x)：要从x开始，不断向上寻找它的父亲，直到找到根为止。UNION（x,y）：只要使一棵树的根指向另一棵树的根即可。第35页/共87页 并查集的树实现 下下图描述了查找一个结点的过程（黑色结点为当前查找结点）。图描述了查找一个结点的过程（黑色结点为当前查找结点）。查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为h h，则算法的时间复杂度为则算法的时间复杂度为O(h)O(h)。第36页/共87页 并查集的树树实现 要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用要
23、完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点为另一个根结点即可，代价为为另一个根结点即可，代价为O(1)O(1)。因此，整个算法的复杂度主要在查找根结。因此，整个算法的复杂度主要在查找根结点部分，为点部分，为O(h)O(h)。第37页/共87页 优化查找与合并算法优化查找与合并算法 前前面面提提到到，分分离离集集合合森森林林的的查查找找与与合合并并的的时时间间复复杂杂度度都都是是O(h)O(h)。也也就就是是说说，查查找找与与合合并并的的时时
24、间间复复杂杂度度主主要要取取决决于于树树的的深深度度。就就平平均均情情况况而而言言，树树的的深深度度应应该该在在loglog2 2n n的的数数量量级级，n n为为结结点点个个数数，所所以以分分离离集集合合森森林林查查找找与与合合并并的的平平均均时时间间复复杂杂度度为为O(logO(log2 2n)n)。但但是是，在在最最坏坏情情况况下下，一一棵棵树树的的深深度度可可能能达达到到n n，如如右右图图。这这时时的的查查找找与与合合并并的的时时间间复复杂杂度度都都达达到到了了O(n)O(n)。这这是是我我们们不不愿愿意意看看到到的的，因因此此必必须想方设法避免出现这种情况。须想方设法避免出现这种情
25、况。为了提高效率，可以考虑在为了提高效率，可以考虑在UNION(x,y)UNION(x,y)和和FIND-FIND-SET(x)SET(x)上做一些文章。上做一些文章。第38页/共87页 优化查找与合并算法优化查找与合并算法优化合并过程优化合并过程 一一棵棵较较平平衡衡的的树树拥拥有有比比较较低低的的深深度度，查查找找和和合合并并的的复复杂杂度度也也就就相相应应较较低低。因因此此，如如果果两两棵棵分分离离集集合合树树A A和和B B，深深度度分分别别为为h hA A和和h hB B，则则若若h hA AhhB B，应应将将B B树树作作为为A A树树的的子子树树；否否则则，将将A A树树作作为
26、为B B树树的的子子树树。总总之之，总总是是深深度度较较小小的的分分离离集集合合树树作作为为子子树树。得得到到的的新新的的分分离离集集合合树树C C的的深深度度h hC C，以以B B树树作作A A树树的的子子树为例，树为例，h hC C=maxh=maxhA A,h,hB B+1+1。这样合并得到的分离集合树，其深度不会超过这样合并得到的分离集合树，其深度不会超过loglog2 2n n，是一个比较平衡，是一个比较平衡的树。因此，查找与合并的时间复杂度也就稳定在的树。因此，查找与合并的时间复杂度也就稳定在O(logO(log2 2n)n)了。了。第39页/共87页 路径压缩优化方法路径压缩优
27、化方法 在在分分离离集集合合森森林林中中，分分离离集集合合是是用用分分离离集集合合树树来来表表示示的的。分分离离集集合合树树是是用用来来联联系系集集合合中中的的元元素素的的，只只要要同同一一集集合合中中的的元元素素在在同同一一棵棵树树上上，不不管管它它们们在在树树中中是是如如何何被被联联系系的的，都都满满足足分分离离集集合合树树的的要要求求。如如下下图图，这这两两棵棵分分离离集集合合树树是是等等价价的的，因因为为它它们们所所包包含含的的元元素素相相同同。显显然然，右右边边那那棵棵树树比比较较“优优秀秀”，因因为为它它具具有有比比较较低低的的深深度度。相相应应地地，查查找找与与合合并并的的时时间
28、间复复杂杂度度也也较较低低。那么，我们就应该使分离集合树尽量向右树的形式靠拢。那么，我们就应该使分离集合树尽量向右树的形式靠拢。优化查找与合并算法优化查找与合并算法优化查找查找过程第40页/共87页 FIND-SET(x)FIND-SET(x)第41页/共87页 这这种种改改变变结结点点所所指指方方向向以以降降低低结结点点深深度度，从从而而缩缩短短查查找找路路径径长长度的方法，叫做度的方法，叫做路径压缩路径压缩。实实现现路路径径压压缩缩的的最最简简单单的的方方法法是是在在查查找找从从待待查查结结点点到到根根结结点点的的路路径径时时走走两两遍遍，第第一一遍遍找找到到树树的的根根结结点点，第第二二
29、遍遍改改变变路路径径上上的的结结点点，使之指向根结点（使它们的父结点为根结点）。使之指向根结点（使它们的父结点为根结点）。使使用用路路径径压压缩缩技技术术后后，大大大大提提高高了了查查找找算算法法的的效效率率。如如果果将将带带路路径径压压缩缩的的查查找找算算法法与与优优化化过过的的合合并并算算法法联联合合使使用用，则则可可以以证证明明，n n次次查查找找最最多多需需要要用用O(nO(n(n)(n)时时间间。(n)(n)是是单单变变量量阿阿克克曼曼函函数数的的逆逆函函数数，它它是是一一个个增增长长速速度度比比loglog2 2n n慢慢得得多多、但但又又不不是是常常数数的的函函数。在一般情况下，
30、数。在一般情况下，(n)4(n)4，可以当作常数看。，可以当作常数看。第42页/共87页路径压缩u这种方法是在FIND-SET(x)过程中作一些改进。设想，从x到它的根，我们必须经过一条路径，显然这条路径上的所有的根与x的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行FIND-SET(x)时，只要经过一步就可以找到根。可以认为是x顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。第43页/共87页可以看到，FIND-SET(x)是一个递归的过程。它的实现非常简洁，同时我们的方
31、法也可以保证递归深度不会很深。事实上，只要使用这两种方法中的任何一种，算法的效率都会大大提高。当两种方法结合起来以后，效率更高，几乎可以接近n的线性复杂度。第44页/共87页优化后的代码：#include#include#define maxn 1000int n,m;int pmaxn;int find(int x)；void makeset()for(int i=1;i=n;i+)pi=i;-初始每颗树根节点都是自己int main()-n表示成员数，m表示关系数 while(scanf(%d%d,&n,&m)!=EOF)makeset();int i,x,y;int g,h;for(i=
32、1;i=m;i+)scanf(%d%d,&x,&y);g=find(x);h=find(y);return 0;第45页/共87页非递归版:int find(int x)/非递归版int g=x,h;while(px!=x)/寻找根节点x=px;while(pg!=x)/路径压缩h=pg;pg=x;g=h;return x;第46页/共87页递归版:int find(int x)/递归版if(x=px)return x;px=find(px);/寻找根节点，同时压缩路径return px;第47页/共87页最小生成树第48页/共87页最小生成树最小生成树 无向连通网络G的所有生成树中，树枝的权
33、值总和最小的树称为G的最小生成树。性质假设一个图中存在最小生成树，并且该图具有n个节点，m条边，则该图的最小生成树一定是含有n个节点，并且具有n-1条边第49页/共87页最小生成树1.Kruskal算法：每次选择一条最小且不会构成回路权边直至构成一个生成树每次选择一条最小且不会构成回路权边直至构成一个生成树2.Prim 算法：从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。图，直至将所有结点加入子图。第50页/共87页行动中的Kru
34、skal算法1234567351030152540201781511211234567第51页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第52页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第53页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第54页/共87页行动中的Kruskal算法1231045
35、30152540206717815351030152540201781511211234567第55页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第56页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第57页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第58页/共87页行动中的Kruskal算法123
36、104530152540206717815351030152540201781511211234567第59页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第60页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第61页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第62页/共87页行动中的Kruskal算
37、法123104530152540206717815351030152540201781511211234567第63页/共87页行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 2 3 4 5 4 73510301525402017815112112357根结点根结点46 664第64页/共87页行动中的Kruskal算法123104530156717815结点结点 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 7351030152540201781511211234567265第65页/共87页行动中的Kru
38、skal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 5351030152540201781511211234567 766第66页/共87页行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 5 4 5 4 5351030152540201781511211234567 7367第67页/共87页行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 4 4 4 4 43510
39、3015254020178151121123456757357368第68页/共87页行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 4 4 4 4 4 4 4351030152540201781511211234567573169第69页/共87页#include#include#include using namespace std;#define maxn 110int pmaxn,n,m;struct node/结构体存储每一条边，便于调用qsort排序函数int u,v;int w;edgemaxn*maxn;bo
40、ol cmp(const node x,const node y)/快排函数sort的排序规则return x.w=y.w;void init()/初始化数据for(int i=1;i=n;i+)pi=i;第70页/共87页int find(int x)/并查集调用，判断新加入这条边之后会不会形成环int g=x,h;while(x!=px)x=px;while(pg!=x)h=pg;pg=x;g=h;return x;第71页/共87页int main()scanf(%d%d,&n,&m);init();int i;for(i=0;i m;i+)scanf(%d%d%d,&edgei.u,&
41、edgei.v,&edgei.w);sort(edge,edge+m,cmp);/c+中的快排函数int sum=0;/标记总权值int k=0;/标记已经加入多少条边了for(i=0;i m&k n-1;i+)/求最小生成树 int g=find(edgei.u),h=find(edgei.v);if(g!=h)pg=h;sum+=edgei.w;k+=1;printf(%dn,sum);return 0;第72页/共87页克鲁斯卡尔算法的时间复杂度为O(eloge).第73页/共87页行动中的行动中的Prim算法算法1233510453015254020671781511214567123
42、从黄色结点到绿色结点的最小代价弧能通从黄色结点到绿色结点的最小代价弧能通过把在优先队列中的弧值替换找到。过把在优先队列中的弧值替换找到。第74页/共87页行动中的行动中的Prim算法算法13354530152540206717815112145671352210251023第75页/共87页20行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302156734第76页/共87页20行动中的行动中的Prim算法算法133545152540671715111352210251024108213082030216817155736
43、4第77页/共87页20行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511735第78页/共87页20行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511735第79页/共87页20行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511375117第80页/共87页20行动中的行动中的P
44、rim算法算法13354515254067171511135221025102410821308203021681715641551511711735153第81页/共87页20行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511711735153第82页/共87页#include#include#include using namespace std;#define INF 0 xffffff#define maxn 110int n,m;int grapmaxnmaxn;/存储图int
45、distmaxn;/记录选中点到没有选中点的最短距离int sum;/记录最小生成树的总权值int premaxn;/标记点是否被选中void init()memset(grap,0,sizeof(grap);memset(pre,0,sizeof(pre);sum=0;第83页/共87页int main()init();scanf(%d%d,&n,&m);int i,x,y,z;for(i=0;i m;i+)scanf(%d%d%d,&x,&y,&z);grapxy=grapyx=z;prim(1);/初始点设为点1printf(%dn,sum);return 0;第84页/共87页void
46、 prim(int u)int i,j;preu=1;/标记点是否被选中过for(i=1;i=n;i+)/初始化，已选中点到没有选中点的最短距离if(grapui)disti=grapui;else disti=INF;for(i=1;i n;i+)int x=-1,maxs=INF;/maxs记录最小距离，x就记录得到最小距离的那个点for(j=1;j=n;j+)if(!pre j&dist j maxs)maxs=dist j;x=j;if(x!=-1)/记录点x被选中，并且在总权值sum中加入maxsprex=1;sum+=maxs;for(j=1;j grapx j&grapx j)d
47、ist j=grapx j;第85页/共87页Prim算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此Prim算法的时间复杂度为O(n )。Prim算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树.kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！2第86页/共87页谢谢大家观赏！第87页/共87页