acm圖論一PPT教學(xué)課件

1、圖論基礎(chǔ)圖論基礎(chǔ) 并查集及其應(yīng)用并查集及其應(yīng)用 最小生成樹：最小生成樹： Kruskal Kruskal算法，算法，PrimPrim算法算法 最短路徑：最短路徑：DijkstraDijkstra算法，算法，F(xiàn)loyedFloyed算法，算法，Bellman-FordBellman-Ford算法算法 EulerEuler回路，回路，HamiltonHamilton回路回路 二分圖的最大匹配二分圖的最大匹配第1頁/共87頁學(xué)習(xí)圖論的誤區(qū)學(xué)習(xí)圖論的誤區(qū)1 1 模板模板只知道每種算法的模板，不深究其中的方法。只知道每種算法的模板，不深究其中的方法。 這樣平時(shí)做題這樣平時(shí)做題時(shí)可以做的省事，但是在比賽時(shí)

2、就會(huì)覺得這個(gè)題是用這個(gè)模板但發(fā)時(shí)可以做的省事，但是在比賽時(shí)就會(huì)覺得這個(gè)題是用這個(gè)模板但發(fā)現(xiàn)不了陷阱一直現(xiàn)不了陷阱一直WAWA。例如最大匹配。例如最大匹配- -最小覆蓋原則，如果只知道最大最小覆蓋原則，如果只知道最大匹配算法模板，遇到一個(gè)最小覆蓋的問題就不會(huì)做了，實(shí)際上這兩匹配算法模板，遇到一個(gè)最小覆蓋的問題就不會(huì)做了，實(shí)際上這兩個(gè)問題是等價(jià)的。如果連定義都說不明白的話，會(huì)顯得你很個(gè)問題是等價(jià)的。如果連定義都說不明白的話，會(huì)顯得你很lowlow。2 2 遞歸與非遞歸遞歸與非遞歸圖論有很多算法可以用遞歸實(shí)現(xiàn)。例如匈牙利算法，遞歸與非圖論有很多算法可以用遞歸實(shí)現(xiàn)。例如匈牙利算法，遞歸與非遞歸實(shí)現(xiàn)都能

3、解決最大匹配問題，而且遞歸可讀性與條例性更強(qiáng)。遞歸實(shí)現(xiàn)都能解決最大匹配問題，而且遞歸可讀性與條例性更強(qiáng)。但在頂點(diǎn)數(shù)量很大時(shí)，非遞歸算法就能體現(xiàn)出他的優(yōu)勢：無須擔(dān)心但在頂點(diǎn)數(shù)量很大時(shí)，非遞歸算法就能體現(xiàn)出他的優(yōu)勢：無須擔(dān)心棧溢出。所以希望，學(xué)有余力的同學(xué)能夠了解一下你所掌握的算法棧溢出。所以希望，學(xué)有余力的同學(xué)能夠了解一下你所掌握的算法的非遞歸實(shí)現(xiàn)。的非遞歸實(shí)現(xiàn)。3 3 徹底明白算法后，每次也只是直接復(fù)制代碼徹底明白算法后，每次也只是直接復(fù)制代碼 這樣的結(jié)果就是：忘的非?？?。非?？臁？?。這樣的結(jié)果就是：忘的非常快。非常快?？?。每次敲代碼都是對(duì)算法的重新復(fù)習(xí)，甚至可以重新審視自己的算法每次敲代碼都

4、是對(duì)算法的重新復(fù)習(xí)，甚至可以重新審視自己的算法實(shí)現(xiàn)，從而優(yōu)化自己的代碼。記得耀哥就敲過這些算法做消遣，而實(shí)現(xiàn)，從而優(yōu)化自己的代碼。記得耀哥就敲過這些算法做消遣，而不是玩掃雷。不是玩掃雷。第2頁/共87頁并查集第3頁/共87頁并查集引例：親戚(relatives)問題或許你并不知道，你的某個(gè)朋友是你的親戚。他可能是你的或許你并不知道，你的某個(gè)朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子！曾祖父的外公的女婿的外甥女的表姐的孫子！如果能得到完整的家譜，如果能得到完整的家譜，判斷兩個(gè)人是否親戚判斷兩個(gè)人是否親戚應(yīng)該是可行的應(yīng)該是可行的，但如果兩個(gè)人的最近公共祖先與他們相隔好幾代，

5、使得家，但如果兩個(gè)人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及。在這種情譜十分龐大，那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及。在這種情況下，最好的幫手就是計(jì)算機(jī)。況下，最好的幫手就是計(jì)算機(jī)。第4頁/共87頁并查集為了將問題簡化，你將得到一些親戚關(guān)系的信息，如為了將問題簡化，你將得到一些親戚關(guān)系的信息，如MarryMarry和和TomTom是親戚，是親戚，TomTom和和BenBen是親戚，等等。從這些信息中，你是親戚，等等。從這些信息中，你可以推出可以推出MarryMarry和和BenBen是親戚。是親戚。請(qǐng)寫一個(gè)程序，對(duì)于有關(guān)親戚關(guān)系的提問，以最快的速度給請(qǐng)寫一個(gè)

6、程序，對(duì)于有關(guān)親戚關(guān)系的提問，以最快的速度給出答案。出答案。 第5頁/共87頁并查集Input:Input:n 第一部分以N N ，M M 開始。N N 為問題涉及的人的個(gè)數(shù)( 1 ( 1 N N 20000)20000)。這些人的編號(hào)為1,2,3,1,2,3, N, N。下面有M M行(1 (1 M M 1 1 000 000)000 000)，每行有兩個(gè)數(shù)a ai i, b, bi i，表示已知a ai i和b bi i是親戚。n 第二部分以Q Q開始。以下Q Q行有Q Q個(gè)詢問(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 對(duì)于每個(gè)詢問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頁問題分析 我們可以將每個(gè)人抽象成為一個(gè)點(diǎn)，數(shù)據(jù)給出M個(gè)邊的關(guān)系，兩個(gè)人是親戚的時(shí)候兩點(diǎn)間有一條邊。很自然地就得到了一個(gè)有N個(gè)頂點(diǎn)M條邊的圖論模型

8、，注意到傳遞關(guān)系，在此無向圖中的一個(gè)連通分支中的任意點(diǎn)之間都是親戚。 對(duì)于最后的Q個(gè)提問，即判斷所提問的兩個(gè)頂點(diǎn)是否在同一個(gè)連通分支中。第8頁/共87頁問題分析 這樣的解題思路很清楚，對(duì)于輸入的N個(gè)點(diǎn)M條邊，建立一個(gè)無向圖（保存邊），找出所有的連通塊（遍歷算法），然后根據(jù)提問逐個(gè)進(jìn)行判斷。 但是本題的數(shù)據(jù)范圍很大，1 N 20000 , 1 M 1 000 000，不管是從空間上看還是從時(shí)間上看，都很難接受。第9頁/共87頁問題分析 再進(jìn)一步考慮，如果把題目的要求改一改，對(duì)于邊和提問相間輸入，即把題目改成：第一行是N，M。N為問題涉及的人的個(gè)數(shù)，下面有M行，每行有三個(gè)數(shù)ki,ai,b，其含義如

9、下：ai和bi表示兩個(gè)元素，ki為0或1ki為1時(shí)，表示這是一條邊的信息，即表示ai和bi是親戚關(guān)系ki為0時(shí)，表示這是一個(gè)提問，要你根據(jù)此行以前所得到的信息，判斷ai和bi是否是親戚，對(duì)于每條提問回答Yes或No。 第10頁/共87頁問題分析 這個(gè)問題比原問題更復(fù)雜些(復(fù)雜在何處?)，需要在任何時(shí)候回答提問的兩個(gè)人的關(guān)系，是一種動(dòng)態(tài)判斷。并且對(duì)于信息提示還要能立即合并兩個(gè)連通分支。采用連通圖思想在實(shí)現(xiàn)上就有點(diǎn)困難，因?yàn)橐獙?shí)時(shí)地表示人與人之間的關(guān)系。第11頁/共87頁問題分析 可以用集合的思路來考慮這個(gè)問題(從邏輯上來看，這的確是個(gè)集合問題)： 對(duì)每個(gè)人都建立一個(gè)集合； 開始的時(shí)候，集合元素是

10、這個(gè)人本身，表示開始時(shí)不知道任何人是他的親戚； 以后每次給出一個(gè)親戚關(guān)系時(shí)，就將兩個(gè)集合合并。這樣實(shí)時(shí)地得到了在當(dāng)前狀態(tài)下的集合關(guān)系。如果有提問，即在當(dāng)前得到的結(jié)果中，看兩個(gè)元素是否屬于同一集合。第12頁/共87頁輸入關(guān)系輸入關(guān)系 分離集合分離集合初始狀態(tài)初始狀態(tài) 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頁 由上圖可以看出，由上圖可以看出，操作是在集合操作是在集合的基礎(chǔ)上進(jìn)行的的基礎(chǔ)上進(jìn)行的，在操作過程中，我，在操作過程中，我們沒有保存任何一條邊，而且每一步們沒有保存任何一條邊，而且每一步得到的劃分方式是動(dòng)態(tài)的。得到的劃分方式是動(dòng)態(tài)的。( (為什么可為什么可以采用集合？用集合還有什么問題？

12、以采用集合？用集合還有什么問題？) ) 如何來實(shí)現(xiàn)以上的算法思想呢？這就如何來實(shí)現(xiàn)以上的算法思想呢？這就用到了用到了并查集并查集這種數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)。并查集的基本思想第14頁/共87頁并查集的基本思想 什么叫并查集？ 并查集（union-find set）是一種用于分離集合(disjoint-set)的操作算法。學(xué)習(xí)一種新算法需要了解哪些方面？（特性/本質(zhì)、存儲(chǔ)表示/實(shí)現(xiàn)、操作、應(yīng)用)。它所處理的是“集合”之間的關(guān)系，即動(dòng)態(tài)地維護(hù)和處理集合元素之間復(fù)雜的關(guān)系。第15頁/共87頁并查集的基本思想 當(dāng)給出兩個(gè)元素的一個(gè)無序?qū)?a, b)時(shí)，需要快速“合并”a和b分別所在的集合，這其間需要反復(fù)

13、“查找”某元素(如a和b)所在的集合，然后才能合并。 “并”、“查”和“集”三字由此而來。第16頁/共87頁并查集的基本思想 在這種數(shù)據(jù)類型中，n個(gè)不同的元素被分為若干組。每組是一個(gè)集合，這種集合叫做分離集合（disjoint set）。 并查集支持查找一個(gè)元素所屬的集合，以及將兩個(gè)元素各自所屬的集合進(jìn)行合并等操作。第17頁/共87頁并查集支持的操作 動(dòng)態(tài)集合中的每一元素是由一個(gè)對(duì)象來表示的，設(shè)x表示一個(gè)對(duì)象，并查集的實(shí)現(xiàn)一般需要支持如下操作： MAKE-SET（x）建立一個(gè)新的集合 UNION（x, y）將包含x和y的動(dòng)態(tài)集合（例如Sx和Sy）合并為一個(gè)新的集合，假定在此操作前這兩個(gè)集合是分

14、離的。 FIND-SET（x） 返回一個(gè)包含x的集合的代表。第18頁/共87頁并查集的實(shí)現(xiàn)及優(yōu)化并查集的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法很多，一般用的比較多的是數(shù)組實(shí)現(xiàn)、鏈表實(shí)現(xiàn)和樹實(shí)現(xiàn)。 第19頁/共87頁并查集的數(shù)組實(shí)現(xiàn) 用數(shù)組si記錄元素 i 所屬集合的編號(hào)。 各操作的實(shí)現(xiàn)如下： MAKE-SET（x）：初始化只需做 si := i; FIND-SET（x）：查找元素所屬的集合時(shí)，只需讀出si，時(shí)間復(fù)雜度為O(1)。 UNION（x, y）：合并兩元素各自所屬的集合時(shí)，需要將數(shù)組中屬于其中一個(gè)集合的元素所對(duì)應(yīng)的數(shù)組元素值全部改為另一個(gè)集合的 編號(hào)值，時(shí)間復(fù)雜度為O(n)。第20頁/共87頁并查集的數(shù)組實(shí)

15、現(xiàn) 實(shí)現(xiàn)簡單，實(shí)際使用較多，但合并的代價(jià)太大。（diaosi用）。 在最壞情況下，所有集合合并成一個(gè)集合的總代價(jià)會(huì)達(dá)到O(n2)（Why?）。 第21頁/共87頁并查集的數(shù)組實(shí)現(xiàn) 輸入樣例：輸入樣例：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頁并查集的鏈表實(shí)現(xiàn) 每個(gè)集合對(duì)應(yīng)一個(gè)鏈表，它有一個(gè)表頭，每一個(gè)元素有一個(gè)指針指向表頭，表明了它所屬的類，另有一個(gè)指針指向它的下一個(gè)元素。 同時(shí)，為了方便實(shí)現(xiàn)，再設(shè)一個(gè)指針last表示鏈表中的最后一個(gè)元素（表尾）。第23頁/共87頁并查集的鏈表實(shí)現(xiàn) 此時(shí)，各并查集操作的實(shí)現(xiàn)如下： MAKE-SET(x)： Sx.head := x; Sx.next := 0; FIND-SET（x）： return Sx.head 兩個(gè)過程的時(shí)間復(fù)雜度都為O(1)。第24頁/共87頁并查集的鏈表實(shí)現(xiàn) UNION(x, y)： 假設(shè)UNION(x, y)的參數(shù)是有序的，即把y屬于

17、的集合合并到x的集合上去，有兩種實(shí)現(xiàn)方法：（1）簡單實(shí)現(xiàn)（2）快速實(shí)現(xiàn) 第25頁/共87頁UNION(x,y)操作的簡單實(shí)現(xiàn) 不考慮任何因素，出現(xiàn)FIND-SET（x） FIND-SET（y）時(shí)，直接將y的表頭接到x的表尾，同時(shí)將y所在集合中所有元素的head值設(shè)為FIND-SET(x)。同時(shí)x的表尾也應(yīng)該設(shè)為原y表的表尾。 注意：last指針其實(shí)只要在表頭結(jié)點(diǎn)中記錄即可，因?yàn)槊恳淮尾榈紽IND-SET（x）都可以得到表頭元素。而鏈表中其他元素重新記錄last是無意義的。第26頁/共87頁UNION(x,y)操作的簡單實(shí)現(xiàn) 我們總是把y接到x里去，那么如果y所在的集合非常大，每次賦值的代價(jià)就會(huì)

18、非常高，考慮輸入數(shù)據(jù)的特殊性，比如出現(xiàn)輸入為： （2，1），（3，1），（4，1）， （5，1），（6，1） ， ，(n,1) 最壞情況下時(shí)間復(fù)雜度為O(n2)。 第27頁/共87頁UNION(x,y)操作的快速實(shí)現(xiàn) 上述簡單實(shí)現(xiàn)非常不理想，針對(duì)y可能比較大的這個(gè)問題，可以很快產(chǎn)生一個(gè)聰明的想法：不妨比較x和y所在集合的大小，從而作出選擇，把較短的鏈表接在較長的尾部，這樣效果是一樣的，但代價(jià)肯定不比原來差。這就是快速實(shí)現(xiàn)的思路。第28頁/共87頁UNION(x,y)操作的快速實(shí)現(xiàn) 可以在node里多設(shè)一個(gè)域number，用來記錄此條鏈表中成員的個(gè)數(shù)。顯然number記錄在表頭元素中即可，將兩表

19、合并的時(shí)候，只要將表的number相加，因此維護(hù)起來是非常方便的。 這種快速實(shí)現(xiàn)的方法可以稱為加權(quán)啟發(fā)式合并，這里的權(quán)就是指所記錄的number。 第29頁/共87頁UNION(x,y)操作的快速實(shí)現(xiàn) 當(dāng)有n個(gè)元素時(shí)，可以證明這種方法的效率在UNION上的花費(fèi)（即重新賦值的次數(shù)）的上界是O(nlog2n)： 考慮一個(gè)固定的對(duì)象x，當(dāng)x的代表指針（head）被更新時(shí)，x必是屬于一個(gè)較小的集合，因此，x的代表指針第一次更新后，結(jié)果集合必然至少有2個(gè)元素。第30頁/共87頁UNION(x,y)操作的快速實(shí)現(xiàn)u類似地，下一次更新后，x所在的集合至少有4個(gè)元素。u繼續(xù)下去，可以發(fā)現(xiàn)，x的代表指針最多被更

20、新log2n次，因?yàn)楫?dāng)x所在集合元素已經(jīng)等于n以后，不可能再發(fā)生UNION操作。u所以，總共有n個(gè)元素時(shí)，操作的總次數(shù)不超過nlog2n次。這就保證了整個(gè)算法的復(fù)雜度是理想的。第31頁/共87頁 并查集的鏈表實(shí)現(xiàn)是一種非常容易接受的算法，并且它并查集的鏈表實(shí)現(xiàn)是一種非常容易接受的算法，并且它的效率也是令人滿意的。其實(shí)，它的思路和數(shù)組完全一樣，的效率也是令人滿意的。其實(shí)，它的思路和數(shù)組完全一樣，所以實(shí)際使用較少。所以實(shí)際使用較少。 合并兩個(gè)集合時(shí)的實(shí)現(xiàn)過程如下：合并兩個(gè)集合時(shí)的實(shí)現(xiàn)過程如下：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頁并查集的樹實(shí)現(xiàn) （重要） 我們用有根樹來表示集合，樹中的每個(gè)結(jié)點(diǎn)包含集合的一個(gè)成員，每棵樹表示一個(gè)集合。 多個(gè)集合形成森林，以每棵樹的樹根作為集合的代表，并且根結(jié)點(diǎn)的父結(jié)點(diǎn)指向其自身，樹上的其他結(jié)點(diǎn)的父結(jié)點(diǎn)指向根結(jié)點(diǎn)。第33頁/共87頁 下圖表示了這種關(guān)系，它包含兩個(gè)集合，即下圖表示了這種關(guān)

22、系，它包含兩個(gè)集合，即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頁并查集的樹實(shí)現(xiàn) 這種樹結(jié)構(gòu)也可以簡單地用靜態(tài)數(shù)組實(shí)現(xiàn)，設(shè)px表示元素 x 所指向的父親。MAKE-SET(x)： px=x;FIND-SET(x)： 要從x開始，不斷向上尋找它的父親，直到找到根為止。UNION（x, y）：只要使一棵樹的根指向另一棵樹的根即可。第35頁/共87頁 并查集的樹實(shí)現(xiàn) 下下圖描述了查找一個(gè)結(jié)點(diǎn)的過程（黑色結(jié)點(diǎn)為當(dāng)前查找結(jié)點(diǎn)）。圖描述了查找一個(gè)結(jié)點(diǎn)的過程（黑色結(jié)點(diǎn)為當(dāng)前查找結(jié)點(diǎn)）。 查找算

23、法的復(fù)雜度取決于查找結(jié)點(diǎn)的深度，假設(shè)查找結(jié)點(diǎn)的深度為查找算法的復(fù)雜度取決于查找結(jié)點(diǎn)的深度，假設(shè)查找結(jié)點(diǎn)的深度為h h，則算法的時(shí)間復(fù)雜度為則算法的時(shí)間復(fù)雜度為O(h)O(h)。 第36頁/共87頁 并查集的樹樹實(shí)現(xiàn) 要完成上述合并，首先要找到兩棵分離集合樹的根結(jié)點(diǎn)，這可以通過調(diào)用要完成上述合并，首先要找到兩棵分離集合樹的根結(jié)點(diǎn)，這可以通過調(diào)用兩次查找算法得到。得到根結(jié)點(diǎn)后，只需改變其中一個(gè)根結(jié)點(diǎn)，令它的父結(jié)點(diǎn)兩次查找算法得到。得到根結(jié)點(diǎn)后，只需改變其中一個(gè)根結(jié)點(diǎn)，令它的父結(jié)點(diǎn)為另一個(gè)根結(jié)點(diǎn)即可，代價(jià)為為另一個(gè)根結(jié)點(diǎn)即可，代價(jià)為O(1)O(1)。因此，整個(gè)算法的復(fù)雜度主要在查找根結(jié)。因此，整個(gè)算

24、法的復(fù)雜度主要在查找根結(jié)點(diǎn)部分，為點(diǎn)部分，為O(h)O(h)。 第37頁/共87頁 優(yōu)化查找與合并算法優(yōu)化查找與合并算法 前面提到，分離集合森林的查找與合并的時(shí)間前面提到，分離集合森林的查找與合并的時(shí)間復(fù)雜度都是復(fù)雜度都是O(h)O(h)。也就是說，查找與合并的時(shí)間復(fù)。也就是說，查找與合并的時(shí)間復(fù)雜度主要取決于樹的深度。就平均情況而言，樹的雜度主要取決于樹的深度。就平均情況而言，樹的深度應(yīng)該在深度應(yīng)該在loglog2 2n n的數(shù)量級(jí)，的數(shù)量級(jí)，n n為結(jié)點(diǎn)個(gè)數(shù)，所以分為結(jié)點(diǎn)個(gè)數(shù)，所以分離集合森林查找與合并的平均時(shí)間復(fù)雜度為離集合森林查找與合并的平均時(shí)間復(fù)雜度為O(logO(log2 2n)n

25、)。但是，在最壞情況下，一棵樹的深度可。但是，在最壞情況下，一棵樹的深度可能達(dá)到能達(dá)到n n，如右圖。這時(shí)的查找與合并的時(shí)間復(fù)雜，如右圖。這時(shí)的查找與合并的時(shí)間復(fù)雜度都達(dá)到了度都達(dá)到了O(n)O(n)。這是我們不愿意看到的，因此必。這是我們不愿意看到的，因此必須想方設(shè)法避免出現(xiàn)這種情況。須想方設(shè)法避免出現(xiàn)這種情況。 為了提高效率，可以考慮在為了提高效率，可以考慮在UNION(x,y)UNION(x,y)和和FIND-FIND-SET(x)SET(x)上做一些文章。上做一些文章。 第38頁/共87頁 優(yōu)化查找與合并算法優(yōu)化查找與合并算法優(yōu)化合并過程優(yōu)化合并過程 一棵較平衡的樹擁有比較低的深度，查

26、找和合并的復(fù)雜度也就相應(yīng)較一棵較平衡的樹擁有比較低的深度，查找和合并的復(fù)雜度也就相應(yīng)較低。因此，如果兩棵分離集合樹低。因此，如果兩棵分離集合樹A A和和B B，深度分別為，深度分別為h hA A和和h hB B，則若，則若h hA AhhB B，應(yīng)，應(yīng)將將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。 這樣合并得到的分離集合樹，其深度不會(huì)超過這樣合并得到的分離集合樹，其深度不會(huì)超過loglog2 2n n，是一個(gè)比較平衡，是一個(gè)比較平衡的樹。因此，查找與合并的時(shí)間復(fù)雜度也就穩(wěn)定在的樹。因此，查找與合并的時(shí)間復(fù)雜度也就穩(wěn)定在O(logO(log2 2n)n)了。了。 第39頁/共87頁 路徑壓縮優(yōu)化方法路徑壓縮優(yōu)化方法 在分離集合森林中，分離集合是用分離集合樹來表示的。分離集合樹是在分離集合森林中，分離集合是用分離集合樹來表示的。分離集合樹是用來聯(lián)系集合中的元素的，只要同一集合中的元素在同一棵樹上，不管它們用來聯(lián)系集合中的元素的，只要同一集合中的元素在同一棵樹上，

28、不管它們?cè)跇渲惺侨绾伪宦?lián)系的，都滿足分離集合樹的要求。如在樹中是如何被聯(lián)系的，都滿足分離集合樹的要求。如下下圖，這兩棵分離集圖，這兩棵分離集合樹是等價(jià)的，因?yàn)樗鼈兯脑叵嗤ｏ@然，右邊那棵樹比較合樹是等價(jià)的，因?yàn)樗鼈兯脑叵嗤ｏ@然，右邊那棵樹比較“優(yōu)秀優(yōu)秀”，因?yàn)樗哂斜容^低的深度因?yàn)樗哂斜容^低的深度。相應(yīng)地，查找與合并的時(shí)間復(fù)雜度也較低。相應(yīng)地，查找與合并的時(shí)間復(fù)雜度也較低。那么，我們就應(yīng)該使分離集合樹盡量向右樹的形式靠攏。那么，我們就應(yīng)該使分離集合樹盡量向右樹的形式靠攏。 優(yōu)化查找與合并算法優(yōu)化查找與合并算法優(yōu)化查找查找過程第40頁/共87頁 r x 1 2 1 r 2 x

29、 FIND-SET(x) FIND-SET(x) 第41頁/共87頁 這種改變結(jié)點(diǎn)所指方向以降低結(jié)點(diǎn)深度，從而縮短查找路徑長這種改變結(jié)點(diǎn)所指方向以降低結(jié)點(diǎn)深度，從而縮短查找路徑長度的方法，叫做度的方法，叫做路徑壓縮路徑壓縮。 實(shí)現(xiàn)路徑壓縮的最簡單的方法是在查找從待查結(jié)點(diǎn)到根結(jié)點(diǎn)的實(shí)現(xiàn)路徑壓縮的最簡單的方法是在查找從待查結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑時(shí)走兩遍路徑時(shí)走兩遍，第一遍找到樹的根結(jié)點(diǎn)，第二遍改變路徑上的結(jié)點(diǎn)，第一遍找到樹的根結(jié)點(diǎn)，第二遍改變路徑上的結(jié)點(diǎn)，使之指向根結(jié)點(diǎn)（使它們的父結(jié)點(diǎn)為根結(jié)點(diǎn)）。，使之指向根結(jié)點(diǎn)（使它們的父結(jié)點(diǎn)為根結(jié)點(diǎn)）。 使用路徑壓縮技術(shù)后，使用路徑壓縮技術(shù)后，大大大大提高了查找算

30、法的效率提高了查找算法的效率。如果。如果將帶路徑壓縮的查找算法與優(yōu)化過的合并算法聯(lián)合使用，則可以證將帶路徑壓縮的查找算法與優(yōu)化過的合并算法聯(lián)合使用，則可以證明，明，n n次查找最多需要用次查找最多需要用O(nO(n(n)(n)時(shí)間。時(shí)間。(n)(n)是單變量阿克曼函是單變量阿克曼函數(shù)的逆函數(shù)，它是一個(gè)增長速度比數(shù)的逆函數(shù)，它是一個(gè)增長速度比loglog2 2n n慢得多、但又不是常數(shù)的函慢得多、但又不是常數(shù)的函數(shù)。在一般情況下，數(shù)。在一般情況下，(n)4(n)4，可以當(dāng)作常數(shù)看。，可以當(dāng)作常數(shù)看。 第42頁/共87頁路徑壓縮u這種方法是在FIND-SET(x)過程中作一些改進(jìn)。設(shè)想，從x到它的

31、根，我們必須經(jīng)過一條路徑，顯然這條路徑上的所有的根與x的根是同一個(gè)根，那么不妨在得到結(jié)果的同時(shí)，順便把這條路上全部節(jié)點(diǎn)的根都改成x的根，也就是說，對(duì)這些節(jié)點(diǎn)進(jìn)行了分散，其結(jié)果是，下一次如果再有這條路上的點(diǎn)進(jìn)行FIND-SET(x)時(shí)，只要經(jīng)過一步就可以找到根?？梢哉J(rèn)為是x順便幫了幫大家的忙，把好處帶給了大家，因此其它節(jié)點(diǎn)以后都省事了。 第43頁/共87頁 可以看到，F(xiàn)IND-SET(x)是一個(gè)遞歸的過程。它的實(shí)現(xiàn)非常簡潔，同時(shí)我們的方法也可以保證遞歸深度不會(huì)很深。 事實(shí)上，只要使用這兩種方法中的任何一種，算法的效率都會(huì)大大提高。當(dāng)兩種方法結(jié)合起來以后，效率更高，幾乎可以接近n的線性復(fù)雜度。 第

32、44頁/共87頁優(yōu)化后的代碼：#include #include #define maxn 1000int n , m;int pmaxn;int find(int x)；void makeset() for(int i = 1; i = n; i+) pi = i;-初始每顆樹根節(jié)點(diǎn)都是自己int main()-n表示成員數(shù)，m表示關(guān)系數(shù) 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) /尋找根節(jié)點(diǎn)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); /尋找根節(jié)點(diǎn) ， 同時(shí)壓縮路徑return px; 第47頁/共87頁最小生成樹第48頁/共87頁最小生成樹最小生成樹 無向連通網(wǎng)絡(luò)G的所有生成樹中

34、，樹枝的權(quán)值總和最小的樹稱為G的最小生成樹。性質(zhì)假設(shè)一個(gè)圖中存在最小生成樹，并且該圖具有n個(gè)節(jié)點(diǎn)，m條邊，則該圖的最小生成樹一定是含有n個(gè)節(jié)點(diǎn)，并且具有n-1條邊第49頁/共87頁最小生成樹1. Kruskal算法：每次選擇一條最小且不會(huì)構(gòu)成回路權(quán)邊直至構(gòu)成一個(gè)生成樹每次選擇一條最小且不會(huì)構(gòu)成回路權(quán)邊直至構(gòu)成一個(gè)生成樹2.Prim 算法：從一個(gè)結(jié)點(diǎn)的子圖開始構(gòu)造生成樹：選擇連接當(dāng)前子圖和子圖外結(jié)點(diǎn)的最小權(quán)邊，將相應(yīng)結(jié)點(diǎn)和邊加入子從一個(gè)結(jié)點(diǎn)的子圖開始構(gòu)造生成樹：選擇連接當(dāng)前子圖和子圖外結(jié)點(diǎn)的最小權(quán)邊，將相應(yīng)結(jié)點(diǎn)和邊加入子圖，直至將所有結(jié)點(diǎn)加入子圖。圖，直至將所有結(jié)點(diǎn)加入子圖。第50頁/共87頁行

35、動(dòng)中的Kruskal算法1234567351030152540201781511211234567第51頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第52頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第53頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第54頁/共87頁行動(dòng)中的Kruskal算法1

36、23104530152540206717815351030152540201781511211234567第55頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第56頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第57頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第58頁/共87頁行動(dòng)中的Kruska

37、l算法123104530152540206717815351030152540201781511211234567第59頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第60頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第61頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815351030152540201781511211234567第62頁/共87頁行動(dòng)中的Kr

38、uskal算法123104530152540206717815351030152540201781511211234567第63頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815結(jié)點(diǎn)結(jié)點(diǎn) 1 2 3 4 5 6 7 首首 1 2 3 4 5 4 73510301525402017815112112357根結(jié)點(diǎn)根結(jié)點(diǎn)46 664第64頁/共87頁行動(dòng)中的Kruskal算法123104530156717815結(jié)點(diǎn)結(jié)點(diǎn) 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 7351030152540201781511211234567265第65頁/共87頁行

39、動(dòng)中的Kruskal算法123104530152540206717815結(jié)點(diǎn)結(jié)點(diǎn) 1 2 3 4 5 6 7 首首 1 4 3 4 5 4 5351030152540201781511211234567 766第66頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815結(jié)點(diǎn)結(jié)點(diǎn) 1 2 3 4 5 6 7 首首 1 4 5 4 5 4 5351030152540201781511211234567 7367第67頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815結(jié)點(diǎn)結(jié)點(diǎn) 1 2 3 4 5 6 7 首首 1 4 4 4 4 4

40、 435103015254020178151121123456757357368第68頁/共87頁行動(dòng)中的Kruskal算法123104530152540206717815結(jié)點(diǎn)結(jié)點(diǎn) 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 /結(jié)構(gòu)體存儲(chǔ)每一條邊 ， 便于調(diào)用qsort排序函數(shù)int u , v;int w

41、;edgemaxn*maxn;bool cmp(const node x , const node y) /快排函數(shù)sort的排序規(guī)則return x.w = y.w;void init() / 初始化數(shù)據(jù)for(int i = 1; i = n; i+)pi = i;第70頁/共87頁int find(int x) /并查集調(diào)用 ， 判斷新加入這條邊之后會(huì)不會(huì)形成環(huán)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+中的快排函數(shù)int sum = 0; /標(biāo)記總權(quán)值int k = 0; /標(biāo)記已經(jīng)加入多少條邊了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頁 克魯斯卡爾算法的時(shí)間復(fù)雜度為O(eloge).第73頁/共87頁行動(dòng)中的行動(dòng)中的Prim算法算法1233510453015254020671781511214567123從黃色結(jié)點(diǎn)到綠色結(jié)點(diǎn)的最小代價(jià)弧能通從黃色結(jié)點(diǎn)到綠色結(jié)點(diǎn)的最小代價(jià)弧能通過把在優(yōu)先隊(duì)列中的弧值替換找到。過把在優(yōu)先隊(duì)列中的弧值替換找到。第74頁/共87頁行動(dòng)中的行動(dòng)中的Prim算法算法13354530152540206717815112145671352210251023第75頁/共87頁20行動(dòng)中的行動(dòng)中的Prim算法算法1335451525406717151113522102510241082130820302156734第76頁/共87頁20行動(dòng)中的行動(dòng)中的Prim算法算法1335451525406717151113522102510241082130820302168171557364第77頁/共87頁20行動(dòng)中的行動(dòng)中的Prim算法算法13354515254067171511135221025102410821308203021681715641551511735第78頁/共87頁20行動(dòng)中的行動(dòng)中的Prim算法算法1335451525406717151113522102510241