acm图论一PPT教学课件

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 000 1 000 000)000)，每行为c ci i, d, di i，表示询问c

7、ci i和d di 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，其含义如

9、下：ai和bi表示两个元素，ki为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

11、,45,768,910(1,2) 1,2,3,45,768,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分别所在的集合，这其间需要反复

13、“查找”某元素(如a和b)所在的集合，然后才能合并。 “并”、“查”和“集”三字由此而来。第16页/共87页并查集的基本思想 在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。 并查集支持查找一个元素所属的集合，以及将两个元素各自所属的集合进行合并等操作。第17页/共87页并查集支持的操作 动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现一般需要支持如下操作： MAKE-SET（x）建立一个新的集合 UNION（x, y）将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分

14、离的。 FIND-SET（x） 返回一个包含x的集合的代表。第18页/共87页并查集的实现及优化并查集的数据结构实现方法很多，一般用的比较多的是数组实现、链表实现和树实现。 第19页/共87页并查集的数组实现 用数组si记录元素 i 所属集合的编号。 各操作的实现如下： MAKE-SET（x）：初始化只需做 si := i; FIND-SET（x）：查找元素所属的集合时，只需读出si，时间复杂度为O(1)。 UNION（x, y）：合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的 编号值，时间复杂度为O(n)。第20页/共87页并查集的数组实

15、现 实现简单，实际使用较多，但合并的代价太大。（diaosi用）。 在最坏情况下，所有集合合并成一个集合的总代价会达到O(n2)（Why?）。 第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

16、 7 8 9 10第22页/共87页并查集的链表实现 每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素。 同时，为了方便实现，再设一个指针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属于

17、的集合合并到x的集合上去，有两种实现方法：（1）简单实现（2）快速实现 第25页/共87页UNION(x,y)操作的简单实现 不考虑任何因素，出现FIND-SET（x） 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所在的集合非常大，每次赋值的代价就会

18、非常高，考虑输入数据的特殊性，比如出现输入为： （2，1），（3，1），（4，1）， （5，1），（6，1） ， ，(n,1) 最坏情况下时间复杂度为O(n2)。 第27页/共87页UNION(x,y)操作的快速实现 上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但代价肯定不比原来差。这就是快速实现的思路。第28页/共87页UNION(x,y)操作的快速实现 可以在node里多设一个域number，用来记录此条链表中成员的个数。显然number记录在表头元素中即可，将两表

19、合并的时候，只要将表的number相加，因此维护起来是非常方便的。 这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的number。 第29页/共87页UNION(x,y)操作的快速实现 当有n个元素时，可以证明这种方法的效率在UNION上的花费（即重新赋值的次数）的上界是O(nlog2n)： 考虑一个固定的对象x，当x的代表指针（head）被更新时，x必是属于一个较小的集合，因此，x的代表指针第一次更新后，结果集合必然至少有2个元素。第30页/共87页UNION(x,y)操作的快速实现u类似地，下一次更新后，x所在的集合至少有4个元素。u继续下去，可以发现，x的代表指针最多被更

20、新log2n次，因为当x所在集合元素已经等于n以后，不可能再发生UNION操作。u所以，总共有n个元素时，操作的总次数不超过nlog2n次。这就保证了整个算法的复杂度是理想的。第31页/共87页 并查集的链表实现是一种非常容易接受的算法，并且它并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实，它的思路和数组完全一样，的效率也是令人满意的。其实，它的思路和数组完全一样，所以实际使用较少。所以实际使用较少。 合并两个集合时的实现过程如下：合并两个集合时的实现过程如下：UNION(x,y) UNION(x,y) x = FIND-SET(x); x = FIND-SET(x

21、); 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 UNION(y,x); else UNION(y,x); 第32页/共87页并查集的树实现 （重要） 我们用有根树来表示集合，树中的每个结点包含集合的一个成员，每棵树表示一个集合。 多个集合形成森林，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点的父结点指向根结点。第33页/共87页 下图表示了这种关系，它包含两个集合，即下图表示了这种关

22、系，它包含两个集合，即b,c,e,hb,c,e,h和和d,f,gd,f,g，它们分别以，它们分别以c c和和f f作为代表：作为代表： c h e b d f g 第34页/共87页并查集的树实现 这种树结构也可以简单地用静态数组实现，设px表示元素 x 所指向的父亲。MAKE-SET(x)： px=x;FIND-SET(x)： 要从x开始，不断向上寻找它的父亲，直到找到根为止。UNION（x, y）：只要使一棵树的根指向另一棵树的根即可。第35页/共87页 并查集的树实现 下下图描述了查找一个结点的过程（黑色结点为当前查找结点）。图描述了查找一个结点的过程（黑色结点为当前查找结点）。 查找算

23、法的复杂度取决于查找结点的深度，假设查找结点的深度为查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为h h，则算法的时间复杂度为则算法的时间复杂度为O(h)O(h)。 第36页/共87页 并查集的树树实现 要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点为另一个根结点即可，代价为为另一个根结点即可，代价为O(1)O(1)。因此，整个算法的复杂度主要在查找根结。因此，整个算

24、法的复杂度主要在查找根结点部分，为点部分，为O(h)O(h)。 第37页/共87页 优化查找与合并算法优化查找与合并算法 前面提到，分离集合森林的查找与合并的时间前面提到，分离集合森林的查找与合并的时间复杂度都是复杂度都是O(h)O(h)。也就是说，查找与合并的时间复。也就是说，查找与合并的时间复杂度主要取决于树的深度。就平均情况而言，树的杂度主要取决于树的深度。就平均情况而言，树的深度应该在深度应该在loglog2 2n n的数量级，的数量级，n n为结点个数，所以分为结点个数，所以分离集合森林查找与合并的平均时间复杂度为离集合森林查找与合并的平均时间复杂度为O(logO(log2 2n)n

25、)。但是，在最坏情况下，一棵树的深度可。但是，在最坏情况下，一棵树的深度可能达到能达到n n，如右图。这时的查找与合并的时间复杂，如右图。这时的查找与合并的时间复杂度都达到了度都达到了O(n)O(n)。这是我们不愿意看到的，因此必。这是我们不愿意看到的，因此必须想方设法避免出现这种情况。须想方设法避免出现这种情况。 为了提高效率，可以考虑在为了提高效率，可以考虑在UNION(x,y)UNION(x,y)和和FIND-FIND-SET(x)SET(x)上做一些文章。上做一些文章。 第38页/共87页 优化查找与合并算法优化查找与合并算法优化合并过程优化合并过程 一棵较平衡的树拥有比较低的深度，查

26、找和合并的复杂度也就相应较一棵较平衡的树拥有比较低的深度，查找和合并的复杂度也就相应较低。因此，如果两棵分离集合树低。因此，如果两棵分离集合树A A和和B B，深度分别为，深度分别为h hA A和和h hB B，则若，则若h hA AhhB B，应，应将将B B树作为树作为A A树的子树；否则，将树的子树；否则，将A A树作为树作为B B树的子树。总之，总是深度较小树的子树。总之，总是深度较小的分离集合树作为子树。得到的新的分离集合树的分离集合树作为子树。得到的新的分离集合树C C的深度的深度h hC C，以，以B B树作树作A A树的树的子树为例，子树为例，h hC C=maxh=maxhA

27、 A,h,hB B+1+1。 这样合并得到的分离集合树，其深度不会超过这样合并得到的分离集合树，其深度不会超过loglog2 2n n，是一个比较平衡，是一个比较平衡的树。因此，查找与合并的时间复杂度也就稳定在的树。因此，查找与合并的时间复杂度也就稳定在O(logO(log2 2n)n)了。了。 第39页/共87页 路径压缩优化方法路径压缩优化方法 在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，

28、不管它们在树中是如何被联系的，都满足分离集合树的要求。如在树中是如何被联系的，都满足分离集合树的要求。如下下图，这两棵分离集图，这两棵分离集合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较“优秀优秀”，因为它具有比较低的深度因为它具有比较低的深度。相应地，查找与合并的时间复杂度也较低。相应地，查找与合并的时间复杂度也较低。那么，我们就应该使分离集合树尽量向右树的形式靠拢。那么，我们就应该使分离集合树尽量向右树的形式靠拢。 优化查找与合并算法优化查找与合并算法优化查找查找过程第40页/共87页 r x 1 2 1 r 2 x

29、 FIND-SET(x) FIND-SET(x) 第41页/共87页 这种改变结点所指方向以降低结点深度，从而缩短查找路径长这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，叫做度的方法，叫做路径压缩路径压缩。 实现路径压缩的最简单的方法是在查找从待查结点到根结点的实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍路径时走两遍，第一遍找到树的根结点，第二遍改变路径上的结点，第一遍找到树的根结点，第二遍改变路径上的结点，使之指向根结点（使它们的父结点为根结点）。，使之指向根结点（使它们的父结点为根结点）。 使用路径压缩技术后，使用路径压缩技术后，大大大大提高了查找算

30、法的效率提高了查找算法的效率。如果。如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明，明，n n次查找最多需要用次查找最多需要用O(nO(n(n)(n)时间。时间。(n)(n)是单变量阿克曼函是单变量阿克曼函数的逆函数，它是一个增长速度比数的逆函数，它是一个增长速度比loglog2 2n n慢得多、但又不是常数的函慢得多、但又不是常数的函数。在一般情况下，数。在一般情况下，(n)4(n)4，可以当作常数看。，可以当作常数看。 第42页/共87页路径压缩u这种方法是在FIND-SET(x)过程中作一些改进。设想，从x到它的

31、根，我们必须经过一条路径，显然这条路径上的所有的根与x的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行FIND-SET(x)时，只要经过一步就可以找到根。可以认为是x顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。 第43页/共87页 可以看到，FIND-SET(x)是一个递归的过程。它的实现非常简洁，同时我们的方法也可以保证递归深度不会很深。 事实上，只要使用这两种方法中的任何一种，算法的效率都会大大提高。当两种方法结合起来以后，效率更高，几乎可以接近n的线性复杂度。 第

32、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 = 1; i = m; i+) scanf(%d %d , &x , &y); g = find

33、(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的所有生成树中

34、，树枝的权值总和最小的树称为G的最小生成树。性质假设一个图中存在最小生成树，并且该图具有n个节点，m条边，则该图的最小生成树一定是含有n个节点，并且具有n-1条边第49页/共87页最小生成树1. Kruskal算法：每次选择一条最小且不会构成回路权边直至构成一个生成树每次选择一条最小且不会构成回路权边直至构成一个生成树2.Prim 算法：从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。图，直至将所有结点加入子图。第50页/共87页行

35、动中的Kruskal算法1234567351030152540201781511211234567第51页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第52页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第53页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第54页/共87页行动中的Kruskal算法1

36、23104530152540206717815351030152540201781511211234567第55页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第56页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第57页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第58页/共87页行动中的Kruska

37、l算法123104530152540206717815351030152540201781511211234567第59页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第60页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第61页/共87页行动中的Kruskal算法123104530152540206717815351030152540201781511211234567第62页/共87页行动中的Kr

38、uskal算法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页行

39、动中的Kruskal算法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

40、 435103015254020178151121123456757357368第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

41、;edgemaxn*maxn;bool 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

42、, &m);init();int i ;for(i = 0; i m; i+) scanf(%d %d %d , &edgei.u , &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 , su

43、m);return 0;第72页/共87页 克鲁斯卡尔算法的时间复杂度为O(eloge).第73页/共87页行动中的行动中的Prim算法算法1233510453015254020671781511214567123从黄色结点到绿色结点的最小代价弧能通从黄色结点到绿色结点的最小代价弧能通过把在优先队列中的弧值替换找到。过把在优先队列中的弧值替换找到。第74页/共87页行动中的行动中的Prim算法算法13354530152540206717815112145671352210251023第75页/共87页20行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302156734第76页/共87页20行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302168171557364第77页/共87页20行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511735第78页/共87页20行动中的行动中的Prim算法算法1335451525406717151113522102510241