算法設計與分析實驗5 并查集法求圖論橋問題

一、實驗目的

二、問題描述

三、實驗要求

四、實驗內容

（一）基準算法

（二）高效算法

五、實驗結論

一、實驗目的

????????1. 掌握圖的連通性。

????????2. 掌握并查集的基本原理和應用。

二、問題描述

????????在圖論中，一條邊被稱為“橋”代表這條邊一旦被刪除，這個圖的連通塊數量會增加。等價地說，一條邊是一座橋當且僅當這條邊不在任何環上，一個圖可以有零或多座橋。現要找出一個無向圖中所有的橋，基準算法為：對于圖中每條邊uv，刪除該邊后，運用BFS或DFS確定u和v是否仍然連通，若不連通，則uv是橋。應用并查集設計一個比基準算法更高效的算法，不要使用Tarjan算法。

? ? ? ? ? ? ? ? ? ?????? ????????????????? ??

? ? ? ? ? ? ? ? ? ??圖1 沒有橋的無向連通圖??????????????圖2 有16個頂點和6個橋的圖（橋以紅色線段標示）

三、實驗要求

????????1. 實現上述基準算法。

????????2. 設計的高效算法中必須使用并查集，如有需要，可以配合使用其他任何數據結構。

????????3. 用圖2的例子驗證算法的正確性，該圖存儲在smallG.txt中，文件中第1行是頂點數，第2行是邊數，后面是每條邊的兩個端點。

????????4. 使用文件mediumG.txt和largeG.txt中的無向圖測試基準算法和高效算法的性能，記錄兩個算法的運行時間。

????????5. 實驗課檢查內容：對于smallG.txt、mediumG.txt、largeG.txt中的無向圖，測試高效算法的輸出結果和運行時間，檢查該代碼，限用C或C++語言編寫。其中smallG.txt和mediumG.txt為必做內容，運行時間在4分鐘內有效，直接在終端輸出結果和運行時間。以smallG.txt為例，輸出如下：

0 1

2 3

2 6

6 7

9 10

12 13

0.002

????????其中，第一行的6表示橋數，接下來的6行分別是6座橋的兩個端點，小端點在前，大端點在后，6座橋按照端點從小到大的順序輸出，最后一行的0.002為整個main函數的運行時間，單位為秒。

四、實驗內容

（一）基準算法

1. 算法描述：

????????根據橋的定義，我們可以知道，一條邊(𝑢, 𝑣)是橋，當且僅當刪除邊(𝒖, 𝒗)后，圖的連通塊數量會增加。我們可以枚舉整個邊集，并依次檢查在刪除每條邊后連通塊數量是否增加。具體我們可以用以下方式實現基準算法：

????????????????使用深度優先搜索算法𝑑𝑓𝑠獲取整張圖的連通塊個數𝑁。

????????????????遍歷整張圖邊集，對于每條邊(𝑢, 𝑣)，首先在圖中將其刪除。

????????????????再次使用深度優先搜索算法𝑑𝑓𝑠獲取整張圖的連通塊個數𝑁′。

????????????????若𝑁′>𝑁，則(𝑢, 𝑣)為橋，否則(𝑢, 𝑣)不為橋。

????????????????將邊(𝑢, 𝑣)恢復。回到步驟 2，直至遍歷完全部邊集。

2、偽代碼：

3. 復雜度分析

????????（1）時間復雜度：不妨設圖中點的數量為𝑛，邊的個數為𝑚。使用𝐷𝐹𝑆的時間復雜度為

𝑂(𝑛 + 𝑚)。又因為一共有𝑚條邊需要進行判斷，所以一共要做𝑚次𝐷𝐹𝑆，總時間復雜度為𝑂(𝑚𝑛 + 𝑚2)。

????????????????對于稀疏圖，因為有𝑚 ∝ 𝑛，所以該算法時間復雜度可表示為𝑂(𝑛2)；

????????????????對于稠密圖，因為有𝑚 ∝ 𝑛2，所以該算法時間復雜度可表示為𝑂(𝑛4)。

???????（2）空間復雜度：我們用鄰接表對整張圖進行儲存，空間復雜度一共為𝑂(𝑛 + 𝑚)。

4. 數據測試分析

????????????? 我們分別取點的數量𝑛 = 1000、2000、3000、4000 和 5000，邊的數量𝑚 = 𝑛作為稀疏，邊的數量𝑚 =n*(n-1)/2作為稠密圖對算法進行測試。

????????????? 為降低偶然性，我們對每組數據重復測試 10 次再取平均值

表 1.1 稀疏圖基準算法運行時間表

點的數量𝑛	1000	2000	3000	4000	5000
實際運行時間(ms)	16.5215	77.4551	197.404	397.095	650.526
理論運行時間(ms)	16.5215	77.32	196.641	388.781	638.223

表 1.2 稠密圖基準算法運行時間表

點的數量𝑛	100	200	300	400	500
實際運行時間(ms)	219.495	4039.62	22930.6	67342	190571
理論運行時間(ms)	219.495	3511.92	19779.095	62190.72	170184.375

????????從上表和上圖可以看出，無論是在稀疏圖還是在稠密圖中，算法實際運行的時間和理論運行時間曲線擬合效果良好

5. 基準算法優化

?????? 一次刪邊操作影響的只是其中一個連通分量，不需要對全圖進行𝐷𝐹𝑆 。所以我們在刪除邊之后，只對所刪除邊的其中一個端點做𝑫𝑭𝑺 ：

如果在深度優先搜索過程中搜索到另一結點，則說明邊的兩個端點在同一連通分支，該邊不是橋。

若從一個端點出發沒有搜到另一個端點，則說明邊的兩個端點不在在同一連通分支，該邊是橋。

偽代碼描述：

耗時對比：

表2.1 稀疏圖中基準算法及優化基準算法運行時間表

點的數量𝑛	1000	2000	3000	4000	5000
未優化(ms)	15.275	84.8875	222.129	433.341	720.145
判斷優化(ms)	9.03036	39.3281	88.6593	167.861	267.835

表 2.2 稠密圖中基準算法及優化基準算法運行時間表

點的數量𝑛	100	200	300	400	500
未優化(ms)	219.495	4039.62	22930.6	67342	190571
判斷優化(ms)	16.631	250.045	1301.25	4629.83	10228.2

????????在進行判斷優化的基礎上，在稀疏圖中，代碼運行效率提升了50%，且點數越多，優化效果越明顯；在稠密圖中，提升效果則更加明顯

（二）高效算法

1. 數據結構介紹

并查集

????????并查集是一種樹型的數據結構，可以解決局部聯通問題。并查集把有聯系的元素放入同一個集合，用集合中的一個“有代表性”的元素來表示整個集合，其中集合內部的關系是用一個𝑓𝑎指針來維護。并查集常見的操作有查詢與合并這兩種操作。

????????查詢操作：查詢即查詢當前兩元素是否在同一集合中。我們可以通過遞歸層層向上訪問，直至訪問到根節點。若兩元素的根節點相同，則說明兩元素在同一集合中。否則不在同一集合中。

????????合并操作：合并即將不在同一集合中的兩個子集合合并為一個集合。對于兩個需要合并的元素，我們首先通過查詢得出兩個集合的根節點，然后修改其中一個根節點的𝑓𝑎指針，使其指向另一集合的根節點即可

路徑壓縮

????????隨著集合元素變多，鏈越來越長，我們想要從底部找到根節點就需要經過層層遞歸，這使得? 操作變得越來越難。既然我們只關心一個元素對應的根節點，那么我們就考慮將集合中每個元素的𝑓𝑎指針直接指向根節點。

????????實現方式就是在查詢的時候，把沿途的每個節點的父節點都設置為根節點，這樣就可以的降低查詢時遞歸向上的查詢深度

STL庫

?????? 向量vector，一個大小可動態變化的順序數組容器

?????? vector 容器一方面可以動態的分配空間，比一般的數組更合理使用空間；另外它有很多基本函數，如push_back()函數類似隊列中的push()函數，size()可以直接返回當前容器長度。因為 vector 可以更方便的使用函數調用和管理空間，高效算法構建鄰接表就通過 vector 實現。

對于大數據量級下的圖結構，如果使用臨近矩陣進行存儲，會造成內存溢出，因此也必須使用鄰接表進行存儲。

2. LCA算法-引入最近公共祖先

?????? 在一棵沒有環的樹上，除根節點外每個節點都有其父節點和祖先節點，最近公共祖先就是兩個節點在這棵樹上深度最大的公共祖先節點。

?????? LCA(Least Common Ancestors)，用于求解兩個節點的最近公共祖先的算法。其可用于最短路徑計算，連通性判斷，圖論問題等。

如上圖，4和6的最近公共祖先為5

?????? 在本實驗中，我們可以利用最近公共祖先（LCA）算法找出生成森林中的環邊，即把找LCA 時經過的邊刪除，生成森林中剩余的邊即為橋。

3. 算法思想

?????? 根據橋的定義和圖論的相關知識，我們可以知道，一條邊是橋當且僅當這條邊不在任何環上才成立。那么我們可以用排除法得到圖中的橋，即用 “總邊 - 環邊”。

???????? 又由圖論知識可以得出，樹是邊數最大的無環圖，若向樹上添加任意一條邊時，必然會形成環，所以我們只需找出生成樹中的環邊，除去這些即為橋。

?????? 基于這一想法，可以先構建生成樹

我們接著枚舉不在生成森林上的所有邊，然后可以利用最近公共祖先（LCA）算法找出生成森林中的環邊，即把找LCA 時經過的邊刪除，生成森林中剩余的邊即為橋。

?????? 對于下圖來說，藍色的邊是非生成森林中的邊，我們對該邊左右兩個節點求LCA：首先比較兩個節點的深度，將深度大的節點跳轉到其父節點，并刪除跳轉時經過的邊（圖中顯示為紅色），重復這個過程直到兩個點跳轉到同一個點，即跳轉到它們的 LCA。可以看到，紅顏色的邊就是利用LCA 算法找出的生成森林中的環邊。但由于有些樹的路徑繁長，可通過并查集進行路徑壓縮提高搜索效率

4. 算法實現

并查集-樸素并查集實現求圖的橋算法實現

查詢操作和路徑壓縮

合并操作? 算法優化

????????合并操作算法優化—按秩合并，通過size向量，記錄每個集合的大小，并在合并時選擇將較小的集合合并到較大的集合上，從而實現有效控制樹的高度，提高并查集的查找效率

LCA算法實現

?????? 并查集+LCA算法求解橋問題的算法實現，首先對整個圖分為不同連通塊進行深度優先搜索，隨后通過LCA尋找最近公共祖先，對形成環的邊進行分析處理，最后剩下邊的數量即為橋的數量。

?????? LCA求解最近公共祖先

路徑壓縮

5. 復雜度分析

????????（1）時間復雜度：最壞情況下當生成樹是一條鏈的時候，此時的時間復雜度為𝑂(𝑛)，故總時間復雜度為𝑂(𝑚𝑛)

????????對于稀疏圖，因為有𝑚 ∝ 𝑛，所以該算法時間復雜度可表示為𝑂(𝑛2)；對于稠密圖，因為有𝑚 ∝ 𝑛2，所以該算法時間復雜度可表示為𝑂(𝑛3)。

?????? 對于大數據量級下的查找操作，經過并查集的路徑壓縮，很快需要查找的節點基本上父節點大部分都已經被設置為最近公共祖先（LCA）。此時，查找的時間會接近O ( 1 ) ，則最終的時間復雜度將接近O（m）

????????（2）空間復雜度：我們用鄰接表對整張圖進行儲存，空間復雜度一共為𝑂(𝑛 + 𝑚)。

6. 數據測試分析

????????我們分別取點的數量𝑛 = 1000、2000、3000、4000 和 5000，邊的數量𝑚 = 𝑛作為稀疏，邊的數量𝑚 =n*(n-1)/2作為稠密圖對算法進行測試。

????????為降低偶然性，我們對每組數據重復測試 10 次再取平均值

表2.1 稀疏圖中高效算法運行時間表

點的數量𝑛	1000	2000	3000	4000	5000
實際運行時間	4.0968	5.9614	7.9826	9.2091	17.4451
理論運行時間	4.0968	16.3872	36.8712	65.5488	102.42

表 2.2 稠密圖中高效算法運行時間表

點的數量𝑛	100	200	300	400	500
實際運行時間	3.7533	22.5624	62.2405	162.192	212.828
理論運行時間	3.7533	30.0264	101.339	240.211	469.163

????????由于𝑂(𝑛2)是算法在稀疏圖的理論上界，是在最壞的情況下才會出現的結果，所以實際運行時間曲線要低于理論運行時間曲線，即 LCA 算法在稀疏圖中時間復雜度的理論上界為𝑂(𝑛2)。由于𝑂(𝑛3)是算法在稠密圖的理論上界，是在生成森林為一條鏈時才會出現的結果，所以實際運行時間曲線要低于理論運行時間曲線，即 LCA 算法在稠密圖的時間復雜度的理論上界為𝑂(𝑛2)。

三） 綜合對比分析

????????將結果綜合分析，如下：

表 圖中各種算法運行時間表