面向大規模圖計算的連通分量算法分析與優化*

白 皓，甘新標，楊文祥,賈孟涵，涂旭平，張一鳴，郭 敏，來 樂，張 意，朱春平

(1.國防科技大學計算機學院,湖南 長沙 410073;2.中國空氣動力研究與發展中心計算空氣動力研究所，四川 綿陽 621000;3.黃岡師范學院計算機學院,湖北 黃岡 438000;4.中國人民解放軍66061部隊,北京 100144)

1 引言

圖作為一種常見的數據結構，可以用來抽象表達現實事物間各種復雜的關聯關系[1]。例如，社交網絡、萬維網等可以采用圖表示。近年來，圖數據的規模不斷增長，根據相關報告顯示，2021年第一季度，Facebook每月活躍用戶為2.85億[2]，騰訊WeChat月活躍用戶達到1.24億[3]，把用戶和其之間的關系抽象為圖中的節點和邊，那么圖中節點的規模達到了數十億，邊的規模更是達到了數千億。圖計算是針對圖數據進行處理和計算，在現實生活的諸多場景中都發揮著重要作用。

從圖中某一節點出發訪遍圖中其余節點，且每個節點僅被訪問一次，這一過程叫做圖的遍歷。無向圖的連通分量，也叫極大連通子圖，指的是每對節點都能通過通路來互相連通的子圖。連通分量算法通過某種方式來求解圖中的連通分量，可以應用于可達性查詢、一致性檢測等眾多場景，通常是大規模圖處理的重要步驟[4]。對連通圖進行遍歷過程中所經過的邊和節點的組合稱為生成樹。非連通圖可分解為多個連通分量，而每個連通分量又各自對應至少一棵生成樹，面向超級計算機的大規模圖計算Graph500[5]測試的目的就是通過大規模圖計算遍歷找到一棵最小生成樹。

如果在連通分量上進行遍歷運算，得到對應于該連通分量的生成樹，就是極大連通子圖的極小連通子圖，這樣，只需要在每個連通分量中選定一個節點作為根節點就可以把整個連通分量遍歷完，連通分量中的其他節點不需要再做遍歷算法根節點的嘗試，可見依靠連通分量可以幫助減少一些不必要的遍歷開銷。在并行計算環境下，在點劃分時把同一個連通分量中的節點劃分到邏輯中相近的物理節點上，可以實現負載均衡，降低通信開銷，加快生成樹的生成。因此，求解非連通無向圖的連通分量成為了加速大規模圖遍歷的重要方法。

在單處理器上，Hopcroft等人[6]使用深度優先搜索DFS(Depth First Search)來求解連通分量，其時間復雜度為O(m+n)，m和n分別是圖中邊和節點的數量。然而這種方法很難并行實現[7]。Hirschberg等人[8 - 10]分別用不同數量級的處理器實現了O(log2n)的時間復雜度。van Scoy等人[11,12]分別提出了時間復雜度為O(n)的并行處理方法。Chen等人[13]提出了一種基于k步上近似的粗糙集算法來求解連通分量，進一步優化了性能。Pedroche等人[14]利用RCM(Reverse Cuthill-McKee)方法實現了時間復雜度為O(m+n)的算法。Kofman等人[15]在特定條件下在基于集合的無向圖中實現了常數級的計算開銷。孫斌[16]對串行算法和多個典型的并行算法進行了比較。Zhang等人[17]提出了性能和擴展性較好的FastSV(Fast Shiloach-Vishkin)算法。Liu等人[18]在PRAM(Parameter Random Access Memory)上實現了時間復雜度為O(logd+log logm/nn)的算法，其中，最大連通分量直徑為d，這為在超算平臺上運行連通分量算法提供了借鑒。Bentert等人[19]基于無線傳感器網絡對連通分量算法進行了討論。Durgut等人[20]則利用連通分量算法對求解網絡通信中圖的破裂程度進行了優化。上述研究將連通分量算法應用于網絡通信，把網絡問題抽象為尋找生成樹或最短路徑問題，根本目的是為了減少不必要的訪問，實現系統的最低能耗。

無向圖連通分量的基礎方法主要有3種:BFS(Breadth First Search)、DFS和并查集算法(Union-Find Algorithm)[21,22]。前兩者都是遍歷算法，通過遍歷圖中所有的節點,得到獨立的子圖,即連通分量。并查集算法是通過指定某一連通分量中的唯一根節點，然后不斷添加新的連通信息，從而找到連通分量。

本文圍繞連通分量算法，著重研究了算法和數據結構的性能等問題，主要有以下貢獻：

(1)對并查集算法和數據結構進行配合度分析，提出捷徑向量算法。

(2)單線程與多線程相結合，利用迭代輪轉對算法進行并行優化。

(3)全面分析比較了BFS、DFS和并查集算法對無向圖連通分量算法的實現性能和應用場景。

2 連通分量算法

廣度優先搜索、深度優先搜索和并查集算法都可實現無向圖連通分量算法，其中廣度優先搜索和深度優先搜索都是利用遍歷的思想對所有相連的節點進行搜索訪問，當以鄰接矩陣作為圖的存儲結構時，其算法復雜度均為O(n2)。并查集算法是通過合并具有等價關系的節點對(即一條邊)，來找到所有的連通分量，其傳統方法實現的時間復雜度是O(fu)，其中f是下文中Find的次數，u是Union的次數。

2.1 用遍歷算法尋找連通分量

BFS算法初始時把所有節點都加載到內存，并遍歷這些節點，每訪問到一個節點，如果其未被訪問過，就以其為根節點執行BFS算法，這樣每次執行BFS算法都會得到一個連通分量。

DFS算法與之類似，所不同的是遍歷過程采用的是DFS算法。

2.2 用并查集算法尋找連通分量

并查集算法在初始狀態時，每個節點的根節點均設置為自身，建立指向自身的指針，自成一棵樹，如圖 1所示。在掃描邊進行迭代的過程中，如果2個節點的指針未指向同一個節點，則改變指針，將2個節點置于同一棵樹中。

Figure 1 Initial state of Union-Find Algorithm圖1 并查集算法初始狀態

該算法主要有2個基本數據操作：(1)查找(Find)：確定節點屬于哪一棵樹，用來確定2個節點是否處于同一棵樹，如圖 2所示，雙箭頭表示掃描到的邊，黑色連接線表示在樹中節點的父子關系，虛線箭頭表示尋找根節點的過程。(2)合并(Union)：如果一條邊的2個節點不屬于同一棵樹，則將2個節點合并到一棵樹中，如圖 3所示。

Figure 2 Operation of finding root node圖2 查找根節點操作

Figure 3 Operation of unioning tree圖3 合并樹操作

利用并查集實現的連通分量算法如算法1所示。

算法1利用并查集算法實現的連通分量算法

Input:edge.bin.//輸入邊數據集

Output:connectedcomponent.//輸出連通分量

initialization;//初始化

functionfind(x);//定義find子函數

whileeinedge.bindo//遍歷邊數據集

//把出現的節點放入節點集合

vertexset.insert(e.v1);

vertexset.insert(e.v2);

end

whileeinedge.bindo//遍歷邊數據集

//尋找2個節點的根節點

xroot=find(e.v1);

yroot=find(e.v2);

/*如果2個節點的根節點不相同，則把一個的根節點置為另一個的子節點*/

ifxroot!=yrootthen

xroot.parent=yroot;

end

end

//輸出連通分量

forvinvertexsetdo

ifson[v].size!=0then

output(connectedcomponent);

end

end

算法中，edge.bin表示從Graph500中生成的二進制邊數據集，connectedcomponent指的是每個連通分量的基本信息，如包含的節點、邊等，e是每次從數據集中讀取的包含邊信息的結構體，v1/v2表示構成邊的2個節點，insert()就是節點載入內存的過程,find()用來查找節點的根節點，parent表示節點的父節點，son[v]表示以v節點為根節點的所有節點。

3 捷徑向量算法

3.1 串行捷徑向量算法

傳統的并查集算法創建的樹可能會不平衡，其優化算法主要有2種，第1種是“按秩合并”，把深度較小的樹(即秩較小的樹)連接到更大的樹上，從而增加樹的平衡性，如圖 4所示。第2種是“捷徑”(Shortcutting)，讓節點從指向父節點改成直接指向根節點，減小樹的層級，如圖 5所示。這2種方法避免了過多的find(·)函數的遞歸次數，在Graph500生成的節點規模為240數據集的條件下，每次遞歸都需要開辟資源來完成子函數的初始化，這無疑是巨大的開銷，因此這2種優化是十分有必要的。這2種優化算法的時間復雜度均是O(kα(k,n)),其中，k表示合并查找的操作次數，n為節點數量，α(k,n)為反Ackermann函數[23 - 25]。

Figure 4 Union by rank圖4 按秩合并

Figure 5 Shortcutting圖5 捷徑操作

雖然2個優化算法的時間復雜度一樣，但如果結合數據結構考慮，性能會有差異。為了更好地結合算法和數據結構的優勢，本文提出了捷徑向量算法。

并查集算法需要建立一個數組來存儲節點的根節點。此外，每棵樹的根節點需要存儲所有子節點即以自己為根的所有節點的信息，這就需要建立一個二維的數據結構，由于涉及節點的按下標隨機訪問，第1維采用向量。對第2維，集合具有排序和去重的開銷，而算法的實現細節中并不需要這樣的功能，故本文不考慮使用集合來實現。對比向量和鏈表的特點，向量的構造函數會把每個元素初始化一遍，訪問時Cache的命中率較高，賦值和訪問速度極快，插入則相對較慢，本文根據數據規模能夠預估一些用向量表示的變量的大小，也避免了在向量插入過程中的擴大容量、拷貝內存和釋放原有內存的操作。而鏈表雖然在按秩合并算法中只改變2個節點的指針，但其缺點也是比較明顯的，一是遍歷時需要用迭代器，訪問迭代器需要進行迭代器越位、有效性、是否指向同一容器等方面的判斷，開銷較大；二是插入時需要改變指針，而向量在插入時雖然需要多次擴容，但這種開銷對整體算法的加速是值得的。

從數據結構與算法結合來看，使用捷徑向量算法時，需要把一棵樹中所有節點的根節點都改換成另一棵樹的根節點，這需要遍歷訪問，向量比鏈表快。按秩合并如果采用鏈表，在更新子節點信息時，只需要改變2個節點的指針，雖然在這方面比向量的遍歷增加子節點要占優，但它在調用子函數find(·)時開辟的新資源比向量不使用子函數的情況要大得多，還需要存儲標志秩大小的rank的結構。綜合考慮，捷徑向量算法省去了多次調用子函數的開銷，性能表現會更好。

捷徑向量算法的過程如圖 6所示，在合并前，2棵樹各自用二維向量來存儲各自的信息，樹根節點是向量最頂端的節點，尾部的箭頭表示新插入節點元素的向量增長方向，當新訪問到的邊的2個節點分別屬于2棵樹時(邊由雙向箭頭表示)，一棵樹所對應的向量被整體復制到另一棵樹的向量尾部，沿增長方向依次插入，所以新加入節點元素的根節點指針均改換為指向目的樹向量的根。

Figure 6 Shortcutting-vector algorithm圖6 捷徑向量算法

3.2 捷徑向量算法與遍歷算法比較

從時間復雜度來講，并查集算法要更快。因此，如果只是為了求基本的連通分量的節點信息，而沒有太多其他需求，就使用并查集算法來實現。

遍歷算法的鄰接表保存了邊的信息，當建立連通分量的時候，可以很自然地把邊的信息表示出來，但鄰接表中存儲了重復的信息，每一條邊的2個節點都存儲了對方的信息，造成了2倍的開銷。而并查集算法在合并時忽略了邊的信息，導致一部分信息的缺失。

在空間開銷方面，遍歷算法需要存儲以下數據結構：鄰接表、狀態數組、正在處理的節點的隊列或棧。在Graph500使用的Kronecker生成圖中，默認的節點平均度數為16，設圖中節點的數量為n，則鄰接表包含了16n規模的整型數據，對應每個節點，建立一個長度與節點數量n相等的狀態數組，還需要維護隊列或棧的大小，其大小分別與BFS生成樹的每層的節點數量或DFS生成樹的層數有關。因此，遍歷算法的空間復雜度為O(n)，n表示節點數量，占用空間隨著參數n的平均增加速率為16。

捷徑向量算法需要存儲以下數據結構：二維子節點向量和根節點數組。各個連通分量的根節點存儲了屬于自己的子節點信息，由于Kronecker生成圖滿足冪律分布的特點且該算法按照擴容因子為2的規則來設置子向量長度，故對節點數量為n的圖，二維子節點向量占據的空間為2m，其中表示邊數量的m滿足如式(1)所示的關系：

lbn

(1)

隨著規模n的增加，占用空間的平均增加速率如式(2)所示：

(2)

由式(1)和式(2)可以得出空間開銷平均增加速率的上限如式(3)所示：

rate<2

(3)

這與遍歷算法平均增加速率16相比更具優勢。雖然在存儲過程中沒有存儲邊的信息，但達到了連通分量算法的基本需求。

并查集算法的合并和查找工作不需要一次性把連通分量中所有節點都找到，利用跳躍式、間斷式的累加操作，來實現連通分量規模的逐步擴大，從局部連通分量擴展到全局連通分量，均可用分布式來實現，可以比較方便地并行化。但是，DFS需要不斷往圖的深處訪問，不能適應在數據爆炸環境下的大圖處理,在訪問時需要把相連的節點一次性地訪問完畢，難以實現分布式化。

此外，遍歷算法還可以作為尋找生成樹的基礎和先導，在不增加算法復雜度的基礎上，可以增加一些標志狀態和判定狀態的邏輯來判定有沒有環的情況，這對后面的工作是十分有意義的。遍歷算法和捷徑向量算法的綜合比較如表1所示。

Table 1 Comparison of traversal algorithmand shortcutting-vector algorithm

3.3 多線程捷徑向量算法

考慮到本文設計的串行算法的實現特點，由算法1可知，對查找操作有4種子情況：

(1)2個節點均已被訪問過，且根節點相同。此時不需要做任何操作，繼續掃描下一條邊。

(2)2個節點均已被訪問過，且根節點不同。

(3)2個節點一個被訪問過，另一個未被訪問過。

(4)2個節點均未被訪問過。

對于情況(2)～(4)，下一步需要進行合并操作，把2個節點放置于同一個根節點之下。

對于情況(1)，僅僅是判斷根節點并跳過本條邊，這與合并操作在算法邏輯上可以實現并行，即使情況(1)中出現了臟讀，即讀到了合并操作正在修改的臟數據，對邊的狀態的判斷出現了差錯，也不會影響結果的準確性。情況(1)與合并操作不需要作為2個事務來嚴格保證原子性，這為利用多線程并行加速提供了機會。

在本文設計的并行算法中，主線程(線程0)仍執行串行捷徑向量算法，但需要其他線程對主線程要處理的邊進行預分類，把不需要主線程處理的邊篩掉，存儲在連續存儲的狀態向量中。雖然主線程在處理邊前仍然需要判斷，但狀態向量的存儲空間是順序存儲，能進行線性連續地訪問，減少了主線程的運行時間。

算法分成2個階段：

(1)串行階段。

令主線程單獨對數據集的一部分執行捷徑向量算法，主要目的是更改若干節點的根信息，為下一步并行地預處理提供必要信息，只有一些節點已經位于相同的根節點下面時，才會出現需要優化訪問的邊。

(2)并行階段。

對數據集的其余部分，多線程進行多輪迭代讀取。主線程創建子線程，與子線程執行不同的操作。完成各自的任務后，執行柵欄同步，再開始新一輪的并行，直到多次輪轉后把數據集處理完畢。

主線程和子線程分配相同大小的數據，子線程對屬于自身的每條邊進行判定，查看其2個節點是否有相同的根節點，設置相應的標志位，如果有，則說明不需要進行進一步處理，否則，需要主線程執行合并操作。

主線程主要分成2個階段：

①處理本段數據。此時任務與子線程完全相同，只是不需要更改標志位，因為這已經是最終的處理結果，設置該步驟的目的是在等待子線程處理時不讓主線程閑置。

②處理剩余數據。當子線程處理完畢對應數據后，由主線程對每個子線程的數據分別進行處理，根據標志位來決定是否執行合并操作，直到把本輪所有數據處理完畢。

并行算法的流程如圖 7所示。

Figure 7 Multi-thread shortcutting-vector algorithm圖7 多線程捷徑向量算法

4 實驗與結果分析

4.1 實驗環境

實驗環境的配置是：Intel(R) Core(TM) i7-7700K CPU @ 4.20 GHz；64 GB內存。操作系統為Ubuntu 16.04.7 LTS。

Graph500數據集采用的是Kronecker生成圖，本文在不同規模的生成圖下進行測試比較，其中，用參數scale來衡量圖的大小，表示圖中包含2scale個節點。

4.2 捷徑向量算法性能分析

本文比較了并查集算法的數據結構與算法的不同組合的性能，如表 2所示，其中scale表示數據集的規模，即圖包含2scale個節點。可以發現，若采用按秩合并，向量和鏈表2個數據結構的時間比較接近，但捷徑向量比另外3種實現方式都要快，在220～225規模均取得了最好的性能，在scale=25(包含225個節點)時，與其他2個性能接近的算法的性能之比分別是1.38倍和1.40倍。因此，捷徑向量算法具有顯著的優越性。

Table 2 Performance comparison of Union-Find Algorithm

4.3 連通分量算法3種實現時空開銷分析

本文比較了3種算法對連通分量算法的時間開銷，如圖 8所示。可以看到BFS和DFS算法性能接近，捷徑向量算法遠好于遍歷算法，在scale=25(包含225個節點)時，其對BFS、DFS的加速比分別為4.76倍和4.70倍，這符合本文的分析和預期。

Figure 8 Time comparison of connected component algorithms圖8 連通分量算法時間開銷比較

本文還測試了3種算法的空間開銷，如圖 9所示。3條折線對應主坐標軸，單位為int，表示占用整型變量的數量，2個長條柱對應次坐標軸，分別是捷徑向量算法的空間開銷占BFS、DFS算法存儲開銷的比例。可以看出，本文算法空間占用為另外2個算法的4.1%～4.6%，且增長趨勢也較慢，有著明顯的優勢。

Figure 9 Storage comparison of connected component algorithms圖9 連通分量算法空間開銷比較

4.4 捷徑向量算法的串并行比較

多線程程序中的可變參數包括：線程數量、并行處理數據比例和多線程并行迭代輪數，在不同的數據規模下，對參數取定若干有代表性的值，進行了多組實驗。結果表明，并行算法與串行算法相比有著明顯的性能提升，隨著數據規模的擴大，并行的加速效果越來越明顯，如圖 10所示。在225節點規模的圖中，加速比達到了1.57倍。

Figure 10 Performance comparison of parallel algorithm and serial algorithm圖10 并行算法與串行算法的性能比較

在本文給定的數據規模下，使用2線程時，程序的性能最好。輪數大多數不大于10，對于并行比例，隨著圖規模的增大，取得最佳性能的并行比例越高，這也說明了并行的加速效果，如表 3所示。

Table 3 Parameter configuration for optimal performance of multi-threaded algorithm

5 結束語

本文針對面向大規模圖遍歷的連通分量算法，以Graph500生成的真實數據集為支撐，進行優化分析。連通分量算法和數據結構的優化，對Graph500測試的加速有著重要意義。連通分量算法找到的極大連通子圖，為Graph500找到BFS最小生成樹提供了輔助，合理利用了數據集節點的局部性，減少了無效的BFS根節點嘗試，提升了節點劃分的有效性，減小了節點間的通信開銷。采用捷徑向量算法對并查集算法進行了優化，并進行了算法和數據結構的協同度分析，對實現連通分量算法的3個基礎算法進行了多維度比較和測試，并利用多線程迭代輪轉進行了并行算法優化。實驗結果表明，所提出的優化方法對其他方案均有著明顯優勢。向量作為一個常見的數據結構在面向圖遍歷的連通分量算法中表現較好，雖然它存在著一些不足，但通過與算法的配合，兩者仍然能發揮出較好的效果。在后續的研究中，可以探索在本文研究成果的基礎上，利用進程和線程混合并行來優化算法，這將極大提高本文算法的可擴展性。