acm图论一.ppt

《acm图论一.ppt》由会员分享，可在线阅读，更多相关《acm图论一.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论基础图论基础 并查集及其应用并查集及其应用 最小生成树最小生成树： Kruskal Kruskal算法算法，PrimPrim算法算法 最短路径：最短路径：DijkstraDijkstra算法，算法，FloyedFloyed算法，算法，Bellman-FordBellman-Ford算法算法 EulerEuler回路，回路，HamiltonHamilton回路回路 二分图的最大匹配二分图的最大匹配学习图论的误区学习图论的误区1 1 模板模板只知道每种算法的模板，不深究其中的方法。只知道每种算法的模板，不深究其中的方法。 这样平时做题时可这样平时做题时可以做的省事，但是在比赛时就会觉得这个题是

2、用这个模板但发现不了陷以做的省事，但是在比赛时就会觉得这个题是用这个模板但发现不了陷阱一直阱一直WAWA。例如最大匹配。例如最大匹配- -最小覆盖原则，如果只知道最大匹配算法模最小覆盖原则，如果只知道最大匹配算法模板，遇到一个最小覆盖的问题就不会做了，实际上这两个问题是等价的。板，遇到一个最小覆盖的问题就不会做了，实际上这两个问题是等价的。如果连定义都说不明白的话，会显得你很如果连定义都说不明白的话，会显得你很lowlow。2 2 递归与非递归递归与非递归图论有很多算法可以用递归实现。例如匈牙利算法，递归与非递归图论有很多算法可以用递归实现。例如匈牙利算法，递归与非递归实现都能解决最大匹配问题

3、，而且递归可读性与条例性更强。但在顶点实现都能解决最大匹配问题，而且递归可读性与条例性更强。但在顶点数量很大时，非递归算法就能体现出他的优势：无须担心栈溢出。所以数量很大时，非递归算法就能体现出他的优势：无须担心栈溢出。所以希望，学有余力的同学能够了解一下你所掌握的算法的非递归实现。希望，学有余力的同学能够了解一下你所掌握的算法的非递归实现。3 3 彻底明白算法后，每次也只是直接复制代码彻底明白算法后，每次也只是直接复制代码 这样的结果就是：忘的非常快。非常快。快。这样的结果就是：忘的非常快。非常快。快。每次敲代码都是对算法的重新复习，甚至可以重新审视自己的算法实现，每次敲代码都是对算法的重新

4、复习，甚至可以重新审视自己的算法实现，从而优化自己的代码。记得耀哥就敲过这些算法做消遣，而不是玩扫雷。从而优化自己的代码。记得耀哥就敲过这些算法做消遣，而不是玩扫雷。并查集并查集引例：亲戚(relatives)问题或许你并不知道，你的某个朋友是你的亲戚。他可能是你的或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！曾祖父的外公的女婿的外甥女的表姐的孙子！如果能得到完整的家谱，如果能得到完整的家谱，判断两个人是否亲戚判断两个人是否亲戚应该是可行的应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家，但如果两个人的最近公共祖先与他们相隔好几代，

5、使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。况下，最好的帮手就是计算机。并查集为了将问题简化，你将得到一些亲戚关系的信息，如为了将问题简化，你将得到一些亲戚关系的信息，如MarryMarry和和TomTom是亲戚，是亲戚，TomTom和和BenBen是亲戚，等等。从这些信息中，你是亲戚，等等。从这些信息中，你可以推出可以推出MarryMarry和和BenBen是亲戚。是亲戚。请写一个程序，对于有关亲戚关系的提问，以最快的速度给请写一个程序，对于有关亲戚关系的提问，以最快的速度给出答案。出答案。 并查集

6、Input:Input:n 第一部分以N N，M M开始。N N为问题涉及的人的个数(1 (1 N N 20000) 20000)。这些人的编号为1,2,3, N1,2,3, N。下面有M M行(1 (1 M M 1 000 000) 1 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 000) 1 000 000)，每行为c ci i, d, di i，表示询问c ci i和d di i是否为亲戚。n输出：n 对于每个询问c ci i, d, di i，

7、输出一行：若c ci i和d di i为亲戚，则输出“Yes”Yes”，否则输出“No”No”。并查集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 问题分析 我们可以将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。很自然地就得到了一个有N个顶点M条边的图论模型，注意到传递关系，在此无向图中的一个连通分支中的任意点之间都是亲戚。 对于最后的Q个提问，即判断所提问的两个顶点是否在

8、同一个连通分支中。问题分析 这样的解题思路很清楚，对于输入的N个点M条边，建立一个无向图（保存边），找出所有的连通块（遍历算法），然后根据提问逐个进行判断。 但是本题的数据范围很大，1 N 20000 , 1 M 1 000 000，不管是从空间上看还是从时间上看，都很难接受。问题分析 再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：第一行是N，M。N为问题涉及的人的个数，下面有M行，每行有三个数ki,ai,b，其含义如下：ai和bi表示两个元素，ki为0或1ki为1时，表示这是一条边的信息，即表示ai和bi是亲戚关系ki为0时，表示这是一个提问，要你根据此行以前所得

9、到的信息，判断ai和bi是否是亲戚，对于每条提问回答Yes或No。 问题分析 这个问题比原问题更复杂些(复杂在何处?)，需要在任何时候回答提问的两个人的关系，是一种动态判断。并且对于信息提示还要能立即合并两个连通分支。采用连通图思想在实现上就有点困难，因为要实时地表示人与人之间的关系。问题分析 可以用集合的思路来考虑这个问题(从逻辑上来看，这的确是个集合问题)： 对每个人都建立一个集合； 开始的时候，集合元素是这个人本身，表示开始时不知道任何人是他的亲戚； 以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中，看两个元素是否属于

10、同一集合。输入关系输入关系 分离集合分离集合初始状态初始状态 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,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(

11、2,3) 1,2,3,45,6,78,910(2,3) 1,2,3,45,6,78,910 由上图可以看出，由上图可以看出，操作是在集合操作是在集合的基础上进行的的基础上进行的，在操作过程中，我，在操作过程中，我们没有保存任何一条边，而且每一步们没有保存任何一条边，而且每一步得到的划分方式是动态的。得到的划分方式是动态的。( (为什么可为什么可以采用集合？用集合还有什么问题？以采用集合？用集合还有什么问题？) ) 如何来实现以上的算法思想呢？这就如何来实现以上的算法思想呢？这就用到了用到了并查集并查集这种数据结构。这种数据结构。并查集的基本思想并查集的基本思想 什么叫并查集？ 并查集（unio

12、n-find set）是一种用于分离集合(disjoint-set)的操作算法。学习一种新算法需要了解哪些方面？（特性/本质、存储表示/实现、操作、应用)。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系。并查集的基本思想 当给出两个元素的一个无序对(a, b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素(如a和b)所在的集合，然后才能合并。 “并”、“查”和“集”三字由此而来。并查集的基本思想 在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。 并查集支持查找一个元素所属的集合，以

13、及将两个元素各自所属的集合进行合并等操作。并查集支持的操作 动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现一般需要支持如下操作： MAKE-SET（x）建立一个新的集合 UNION（x, y）将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。 FIND-SET（x） 返回一个包含x的集合的代表。并查集的实现及优化并查集的数据结构实现方法很多，一般用的比较多的是数组实现、链表实现和树实现。 并查集的数组实现 用数组si记录元素 i 所属集合的编号。 各操作的实现如下： MAKE-SET（x）：初始化只需做 si := i; F

14、IND-SET（x）：查找元素所属的集合时，只需读出si，时间复杂度为O(1)。 UNION（x, y）：合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的 编号值，时间复杂度为O(n)。并查集的数组实现 实现简单，实际使用较多，但合并的代价太大。（diaosi用）。 在最坏情况下，所有集合合并成一个集合的总代价会达到O(n2)（Why?）。 并查集的数组实现 输入样例：输入样例：10 710 72 42 45 75 71 31 38 98 91 21 25 65 62 32 33 33 43 47 107 108 98 9UNIONUNION

15、（x,yx,y）过程演示）过程演示：S S1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10S S1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10并查集的链表实现 每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素。 同时，为了方便实现，再设一个指针last表示链表中的最后一个元素（表尾）。并查集的链表实现 此时，各并查集操作的实现如下： MAKE-SET(x)： Sx.head := x; Sx.next := 0; FIND-SET（x）： return Sx.he

16、ad 两个过程的时间复杂度都为O(1)。并查集的链表实现 UNION(x, y)： 假设UNION(x, y)的参数是有序的，即把y属于的集合合并到x的集合上去，有两种实现方法：（1）简单实现（2）快速实现 UNION(x,y)操作的简单实现 不考虑任何因素，出现FIND-SET（x） FIND-SET（y）时，直接将y的表头接到x的表尾，同时将y所在集合中所有元素的head值设为FIND-SET(x)。同时x的表尾也应该设为原y表的表尾。 注意：last指针其实只要在表头结点中记录即可，因为每一次查到FIND-SET（x）都可以得到表头元素。而链表中其他元素重新记录last是无意义的。UNI

17、ON(x,y)操作的简单实现 我们总是把y接到x里去，那么如果y所在的集合非常大，每次赋值的代价就会非常高，考虑输入数据的特殊性，比如出现输入为： （2，1），（3，1），（4，1）， （5，1），（6，1） ， ，(n,1) 最坏情况下时间复杂度为O(n2)。 UNION(x,y)操作的快速实现 上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但代价肯定不比原来差。这就是快速实现的思路。UNION(x,y)操作的快速实现 可以在node里多设一个域number，用来记录此

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

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

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

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

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

23、找与合并算法优化查找与合并算法 前面提到，分离集合森林的查找与合并的时间前面提到，分离集合森林的查找与合并的时间复杂度都是复杂度都是O(h)O(h)。也就是说，查找与合并的时间复。也就是说，查找与合并的时间复杂度主要取决于树的深度。就平均情况而言，树的杂度主要取决于树的深度。就平均情况而言，树的深度应该在深度应该在loglog2 2n n的数量级，的数量级，n n为结点个数，所以分为结点个数，所以分离集合森林查找与合并的平均时间复杂度为离集合森林查找与合并的平均时间复杂度为O(logO(log2 2n)n)。但是，在最坏情况下，一棵树的深度可。但是，在最坏情况下，一棵树的深度可能达到能达到n

24、n，如右图。这时的查找与合并的时间复杂，如右图。这时的查找与合并的时间复杂度都达到了度都达到了O(n)O(n)。这是我们不愿意看到的，因此必。这是我们不愿意看到的，因此必须想方设法避免出现这种情况。须想方设法避免出现这种情况。 为了提高效率，可以考虑在为了提高效率，可以考虑在UNION(x,y)UNION(x,y)和和FIND-FIND-SET(x)SET(x)上做一些文章。上做一些文章。 优化查找与合并算法优化查找与合并算法优化合并过程优化合并过程 一棵较平衡的树拥有比较低的深度，查找和合并的复杂度也就相应较一棵较平衡的树拥有比较低的深度，查找和合并的复杂度也就相应较低。因此，如果两棵分离集

25、合树低。因此，如果两棵分离集合树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 A,h,hB B+1+1。 这样合并得到的分离集合树，其深度不会超过这样合并得到的分离集合树，其深度不会超过

26、loglog2 2n n，是一个比较平衡，是一个比较平衡的树。因此，查找与合并的时间复杂度也就稳定在的树。因此，查找与合并的时间复杂度也就稳定在O(logO(log2 2n)n)了。了。 路径压缩优化方法路径压缩优化方法 在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在树中是如何被联系的，都满足分离集合树的要求。如在树中是如何被联系的，都满足分离集合树的要求。如下下图，这两棵分离集图，这

27、两棵分离集合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较“优秀优秀”，因为它具有比较低的深度因为它具有比较低的深度。相应地，查找与合并的时间复杂度也较低。那。相应地，查找与合并的时间复杂度也较低。那么，我们就应该使分离集合树尽量向右树的形式靠拢。么，我们就应该使分离集合树尽量向右树的形式靠拢。 优化查找与合并算法优化查找与合并算法优化优化查找查找过程过程 r x 1 2 1 r 2 x FIND-SET(x) FIND-SET(x) 这种改变结点所指方向以降低结点深度，从而缩短查找路径长这种改变结点所指方向以降低结点深度

28、，从而缩短查找路径长度的方法，叫做度的方法，叫做路径压缩路径压缩。 实现路径压缩的最简单的方法是在查找从待查结点到根结点的实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍路径时走两遍，第一遍找到树的根结点，第二遍改变路径上的结点，第一遍找到树的根结点，第二遍改变路径上的结点，使之指向根结点（使它们的父结点为根结点）。，使之指向根结点（使它们的父结点为根结点）。 使用路径压缩技术后，使用路径压缩技术后，大大大大提高了查找算法的效率提高了查找算法的效率。如果。如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明

29、，明，n n次查找最多需要用次查找最多需要用O(n(n)O(n(n)时间。时间。(n)(n)是单变量阿克曼函是单变量阿克曼函数的逆函数，它是一个增长速度比数的逆函数，它是一个增长速度比loglog2 2n n慢得多、但又不是常数的函慢得多、但又不是常数的函数。在一般情况下，数。在一般情况下，(n)4(n)4，可以当作常数看。，可以当作常数看。 路径压缩u 这种方法是在FIND-SET(x)过程中作一些改进。设想，从x到它的根，我们必须经过一条路径，显然这条路径上的所有的根与x的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x的根，也就是说，对这些节点进行了分散，其结果

30、是，下一次如果再有这条路上的点进行FIND-SET(x)时，只要经过一步就可以找到根。可以认为是x顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。 可以看到，FIND-SET(x)是一个递归的过程。它的实现非常简洁，同时我们的方法也可以保证递归深度不会很深。 事实上，只要使用这两种方法中的任何一种，算法的效率都会大大提高。当两种方法结合起来以后，效率更高，几乎可以接近n的线性复杂度。 优化后的代码：#include #include #define maxn 1000int n , m;int pmaxn;int find(int x)；void makeset() for(i

31、nt 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(x); h = find(y); return 0;非递归版: int find(int x) /非递归版 int g = x , h;while(px != x) /寻找根节点x = px;while(pg

32、!= x) /路径压缩h = pg;pg = x;g = h;return x; 递归版: int find(int x) /递归版 if(x = px) return x;px = find(px); /寻找根节点 ， 同时压缩路径return px; 最小生成树最小生成树最小生成树 无向连通网络G的所有生成树中，树枝的权值总和最小的树称为G的最小生成树。性质假设一个图中存在最小生成树，并且该图具有n个节点，m条边，则该图的最小生成树一定是含有n个节点，并且具有n-1条边最小生成树1. Kruskal算法：每次选择一条最小且不会构成回路权边直至构成每次选择一条最小且不会构成回路权边直至构成一

33、个生成树一个生成树2.Prim 算法：从一个结点的子图开始构造生成树：选择连接当从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。边加入子图，直至将所有结点加入子图。行动中的Kruskal算法1234567351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法1231045301525402067178153510301

34、52540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Krusk

35、al算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法1231045301525402067178153510

36、30152540201781511211234567行动中的Kruskal算法123104530152540206717815351030152540201781511211234567行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 2 3 4 5 4 73510301525402017815112112357根结点根结点46 665行动中的Kruskal算法123104530156717815结点结点 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 735103015254020178151121123456

37、7266行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 5351030152540201781511211234567 767行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 5 4 5 4 5351030152540201781511211234567 7368行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 1 4 4 4 4 4 435103015254

38、020178151121123456757357369行动中的Kruskal算法123104530152540206717815结点结点 1 2 3 4 5 6 7 首首 4 4 4 4 4 4 4351030152540201781511211234567573170#include #include #include using namespace std;#define maxn 110int pmaxn , n , m;struct node /结构体存储每一条边 ， 便于调用qsort排序函数int u , v;int w;edgemaxn*maxn;bool cmp(const n

39、ode x , const node y) /快排函数sort的排序规则return x.w = y.w;void init() / 初始化数据for(int i = 1; i = n; i+)pi = i;int find(int x) /并查集调用 ， 判断新加入这条边之后会不会形成环int g = x , h;while(x != px)x = px;while(pg != x)h = pg;pg = x;g = h;return x;int main() scanf(%d %d , &n , &m);init();int i ;for(i = 0; i m; i+) scanf(%d

40、%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 , sum);return 0; 克鲁斯卡尔算法的时间复杂度为O(eloge).行动中的行动中的Prim算

41、法算法1233510453015254020671781511214567123从黄色结点到绿色结点的最小代价弧能通从黄色结点到绿色结点的最小代价弧能通过把在优先队列中的弧值替换找到。过把在优先队列中的弧值替换找到。行动中的行动中的Prim算法算法1335453015254020671781511214567135221025102320行动中的行动中的Prim算法算法133545152540671715111352210251024108213082030215673420行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203

42、0216817155736420行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302168171564155151173520行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302168171564155151173520行动中的行动中的Prim算法算法1335451525406717151113522102510241082130820302168171564155151137511720行动中的行动中的Prim算法算法1335451525406717

43、151113522102510241082130820302168171564155151171173515320行动中的行动中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511711735153#include #include #include using namespace std;#define INF 0 xffffff#define maxn 110int n , m;int grapmaxnmaxn; /存储图int distmaxn; /记录选中点到没有选中点的最短距离int sum ;

44、 /记录最小生成树的总权值int premaxn; /标记点是否被选中void init()memset(grap , 0 , sizeof(grap);memset(pre , 0 , sizeof(pre);sum = 0;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;void prim(int u

45、)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(!prej & distj maxs ) maxs = distj;x = j;if(x != -1) /记录点x被选中 ， 并且在总权值sum中加入maxsprex =

46、1;sum += maxs;for(j = 1; j grapxj & grapxj)distj = grapxj; Prim算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此Prim算法的时间复杂度为O(n )。Prim算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树. kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！2