數(shù)據(jù)結(jié)構(gòu)計算機(jī)領(lǐng)域本科教育教學(xué)改革試點工作計劃（“101計劃”）研究成果101不相交集第9章陳鍵飛清華大學(xué)9.1 問題引入9.2 等價關(guān)系、等價類和不相交集9.3 不相交集的存儲實現(xiàn)9.4 不相交集的基本運(yùn)算實現(xiàn)9.5 不相交集的應(yīng)用9.6 拓展延伸9.7 應(yīng)用場景9.1問題引入：Kruskal算法的高效實現(xiàn)9.1問題引入數(shù)據(jù)結(jié)構(gòu)

BCFADGE1081237616514924第1步：選取<E,F>BCFADGE1081237616514924BCFADGE1081237616514924第2步：選取<C,D>BCFADGE1081237616514924第3步：選取<D,E>BCFADGE1081237616514924第4步：選取<B,F>BCFADGE1081237616514924第5步：選取<E,G>BCFADGE1081237616514924第6步：選取<A,B>9.1問題引入：Kruskal算法的高效實現(xiàn)9.1問題引入數(shù)據(jù)結(jié)構(gòu)

9.1問題引入：Kruskal算法的高效實現(xiàn)9.1問題引入數(shù)據(jù)結(jié)構(gòu)注意：只需要查詢頂點之間是否連通，不關(guān)心它們具體通過哪條路徑連通此外，只需要支持加邊操作，而不需要支持刪邊操作。這種情況下，與其完整地維護(hù)無向圖的結(jié)構(gòu)，不如直接維護(hù)連通分量構(gòu)成的集合每個連通分量用其中頂點的集合表示。

1初始時，每個頂點都是獨(dú)立的連通分量，此時有??個僅包含單一頂點的集合：{??_1},{??_2},…,{??_??}2每加入一條邊(??,??)，就將??所屬的集合和??所屬的集合合并3對于連通性查詢(??,??)，只需查詢??和??是否在同一集合中連通性查詢問題變成了維護(hù)若干不相交的集合，并動態(tài)地合并、查找的問題。9.1問題引入：Kruskal算法的高效實現(xiàn)9.1問題引入數(shù)據(jù)結(jié)構(gòu)

9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)不相交集與數(shù)學(xué)中等價關(guān)系、等價類的概念密切相關(guān)元素之間的等價關(guān)系自然地定義了若干不相交集的集合因此，不相交集常常用于處理等價性查詢的問題例如，兩個頂點在同一連通分量中就可以看做一種等價性9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)

9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)

例9.1.不同問題中的等價關(guān)系：1

2

3對于所有生物構(gòu)成的集合，兩種生物是否屬于同一科構(gòu)成一個等價關(guān)系9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)

對集合中的任意元素，稱所有與其等價的元素為一個等價類：

等價關(guān)系把集合劃分成若干個不相交的等價類，每個等價類中的元素互相等價。

稱所有等價類構(gòu)成的集合為一個商集。

商集是一系列集合，這些集合彼此不相交，并且其并集是全集X。這與不相交集的概念恰好對應(yīng)。9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)

9.2等價關(guān)系、等價類和不相交集9.2等價關(guān)系、等價類和不相交集數(shù)據(jù)結(jié)構(gòu)

不相交集可以用于等價性的動態(tài)查詢。

等價性的查詢在計算機(jī)科學(xué)中有廣泛應(yīng)用。例如，在編譯器的設(shè)計中，用于判斷符號地址的等價性。

等價關(guān)系的增加對應(yīng)Union操作，即將兩個等價類合并

9.3不相交集的存儲實現(xiàn)9.3不相交集的存儲實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

不相交集數(shù)據(jù)結(jié)構(gòu)定義：

例：考慮集合X={1,2,3,4,5,6,7,8}。合法的劃分：{{1,2,3,4,5},{6,7},{8}}或{{1}{2},{3},{4},{5},{6},{7},{8}}；以下不是集合X的劃分:{{1,2,3,4,5},{6,7}}和{{1,2,3},{3,4,5},{5,6,7,8}}。

9.3不相交集的存儲實現(xiàn)9.3不相交集的存儲實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

不相交集的數(shù)據(jù)結(jié)構(gòu)需要動態(tài)處理集合的合并和查詢操作，其ADT定義如下：

9.3不相交集的存儲實現(xiàn)9.3不相交集的存儲實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4不相交集的基本運(yùn)算實現(xiàn)9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4不相交集的基本運(yùn)算實現(xiàn)9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4不相交集的基本運(yùn)算實現(xiàn)9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

樸素的不相交集實現(xiàn)的最壞情況

9.4.1按秩合并9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.1按秩合并9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

采取按秩合并策略后，InitSet和Union操作的實現(xiàn)調(diào)整為算法9-4、算法9-5：

9.4.1按秩合并9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.1按秩合并9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

路徑壓縮9.4.2路徑壓縮9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.2路徑壓縮9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

路徑壓縮

9.4.2路徑壓縮9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)下圖演示了同時采用按秩合并和路徑壓縮策略時，8個元素構(gòu)成的不相交集的合并過程。

InitSet(8){1}{2}{3}{4}{5}{6}{7}{8}

Union(6,2){1,5}{2,6}{3}{4}{7}{8}

Union(5,1){1,5}{2}{3}{4}{6}{7}{8}

{1,5}{2,6}{3}{4}{7}{8}

Union(6,5){1,2,5,6}{3}{4}{7}{8}

{1,2,5,6}{3}{4}{7}{8}

{1,2,5,6}{3}{4}{7}{8}

{1,2,5,6}{3}{4}{7}{8}

Union(4,3){1,2,5,6}{3,4}{7}{8}

Union(8,7){1,2,5,6}{3,4}{7,8}

{1,2,5,6}{3,4}{7,8}

{1,2,5,6}{3,4,7,8}

Union(7,3){1,2,3,4,5,6,7,8}

Union(3,6){1,2,3,4,5,6,7,8}

采用了按秩合并和路徑壓縮的不相交集運(yùn)行示例{1,2,5,6}{3,4,7,8}

初始時，所有結(jié)點均不相連，結(jié)點的秩均為0Union(5,1)時，兩結(jié)點具有相同的秩，此時將5合并到1，并將結(jié)點的秩置為1Union(6,5)時，兩棵秩為1的樹合并成為一棵秩為2的樹Union(3,6)時，首先執(zhí)行的Find(6)進(jìn)行了路徑壓縮，將6直接連接至1合并操作將兩棵秩為2的樹合并成一棵秩為3的樹樹有??^??=??個結(jié)點，在可能出現(xiàn)的秩為3的樹中是結(jié)點數(shù)目最少的*此時2成為葉子結(jié)點，但其秩未發(fā)生改變。結(jié)點1的秩也仍是29.4.2路徑壓縮9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.2路徑壓縮9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

Union操作分為找到根結(jié)點的Find操作和將兩棵已知根結(jié)點的子樹合并的操作，將后者稱為Link操作。由于一個Union操作僅包含常數(shù)個Find/Link操作，因此Union操作的均攤時間復(fù)雜度與Find/Link操作的時間復(fù)雜度相同。

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

1

2

3

4

5

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)現(xiàn)在，時間復(fù)雜度分析需要的所有工具都已經(jīng)準(zhǔn)備完畢，下面給出本節(jié)的主要結(jié)論：

9.4.3時間復(fù)雜度分析

9.4不相交集的基本運(yùn)算實現(xiàn)數(shù)據(jù)結(jié)構(gòu)

9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)

最近公共祖先問題蠻力算法的壞情況9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)

最近公共祖先問題蠻力算法的壞情況9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)

9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)

9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)

在算法的執(zhí)行過程中，我們維護(hù)了兩個數(shù)組visited和ancestor。

其中visited表示結(jié)點是否訪問完成，用以判斷詢問是否可完成。ancestor表示結(jié)點集合（子樹）的根。這是因為在采用了按秩合并策略后，F(xiàn)ind找到的“根”并不一定是子樹實際的根，因此需要額外記錄實際的根。9.5不相交集的應(yīng)用：最近公共祖先問題9.5不相交集的應(yīng)用數(shù)據(jù)結(jié)構(gòu)右圖是算法運(yùn)行過程的示意圖。

本例中有4個詢問：分別為LCA(4,5)、LCA(4,6)、LCA(4,2)和LCA(4,7)。

右圖中依次展示了結(jié)點4,5,3,6,2,7的孩子訪問完成，即將輸出LCA時刻的場景，對應(yīng)算法9-7第7行。調(diào)用棧1

LCA(1)調(diào)用棧1

LCA(2)LCA(1)調(diào)用棧1

LCA(3)LCA(2)LCA(1)調(diào)用棧1

LCA(4)LCA(3)LCA(2)LCA(1)調(diào)用棧1

LCA(4)LCA(3)LCA(2)LCA(1)調(diào)用棧1

LCA(4)LCA(3)LCA(2)LCA(1)Ancestor=3（3,4）調(diào)用棧1

LCA(4)LCA(3)LCA(2)LCA(1)調(diào)用棧1

LCA(3)LCA(2)LCA(1)Ancestor=3（3,4）調(diào)用棧1

LCA(5)LCA(3)LCA(2)LCA(1)Ancestor=3（3,4）調(diào)用棧1

LCA(3)LCA(2)LCA(1)Ancestor=3（3,4,5）調(diào)用棧1

LCA(5)LCA(3)LCA(2)LCA(1)Ancestor=3（3,4,5）輸出LCA(4,5)=3調(diào)用棧1

LCA(3)LCA(2)LCA(1)Ancestor=3（3,4,5）調(diào)用棧1

LCA(3)LCA(2)LCA(1)Ancestor=2（2,3,4,5）調(diào)用棧1

LCA(2)LCA(1)Ancestor=2（2,3,4,5）調(diào)用棧1

LCA(6)LCA(2)LCA(1)Ancestor=2（2,3,4,5）調(diào)用棧1

LCA(6)LCA(2)LCA(1)Ancestor=2（2,3,4,5,6）輸出LCA(4,6)=2調(diào)用棧1

LCA(2)LCA(1)Ancestor=2（2,3,4,5,6）輸出LCA(4,2)=2調(diào)用棧1

LCA(2)LCA(1)Ancestor=2（2,3,4,5,6）調(diào)用棧1

LCA(2)LCA(1)Ancestor=2（2,3,4,5,6）調(diào)用棧

LCA(2)LCA(1)Ancestor=1（1,2,3,4,5,6）調(diào)用棧

LCA(1)Ancestor=1（1,2,3,4,5,6）輸出LCA(4,7)=1調(diào)用棧

LCA(7)LCA(1)Ancestor=1（1,2,3,4,5,6）算法首先從根結(jié)點開始遍歷經(jīng)過結(jié)點1,2,3,4在結(jié)點4遍歷完成后，將其合并至父親3。此時結(jié)點3、4同屬于一個集合。

以此類推，算法不斷合并遍歷路徑上的結(jié)點，并正確計算LCA。*取決于不相交集的實現(xiàn)，3、4均可能是該集合的代表元素。不失一般性設(shè)Find(3)=Find(4)=3，則此時ancestor[3]=3。*算法輸出(4,5)的LCA為ancestor[Find(4)]=ancestor[3]=39.6拓展延伸：擴(kuò)展不相交集

9.6拓展延伸數(shù)據(jù)結(jié)構(gòu)

9.6拓展延伸：擴(kuò)展不相交集

9.6拓展延伸數(shù)據(jù)結(jié)構(gòu)

這個問題可以通過不相交集來解決，思路如下：1

2

3

4

5在路徑壓縮時，由于結(jié)點父親有所變化，需要動態(tài)維護(hù)diff。6

7

*通過本例，可以了解如何在不相交集的森林上維護(hù)一些額外的信息，來處理集合元素之間的數(shù)量關(guān)系。9.7應(yīng)用場景:面向?qū)ο蟮木幊陶Z言9.7應(yīng)用場景數(shù)據(jù)結(jié)構(gòu)不相交集在許多計算機(jī)科學(xué)的真實問題上有應(yīng)用。如離線最小值查詢，求控制流圖的支配樹，類型推斷，實現(xiàn)屬性文法（PropertyGrammar）等。近年來，該數(shù)據(jù)結(jié)構(gòu)在圖像處理，數(shù)據(jù)庫和量子計算等領(lǐng)域也有應(yīng)用。

這里介紹不相交集在面向?qū)ο蟮木幊陶Z言中的應(yīng)用。三個類間的繼承關(guān)系

9.7應(yīng)用場景:面向?qū)ο蟮木幊陶Z言9.7應(yīng)用場景數(shù)據(jù)結(jié)構(gòu)面向?qū)ο?/p>