基于Tarjan算法的極大點連通子圖研究

付海奎 陳國軍 王文波

摘要：由于傳統樸素算法求解無向圖的雙連通分量時間花費過高，為了在線性時間內求出雙連通分量并得到極大連通子圖。文章對Tarjan算法的思想以及具體實現做出了詳細的分析。同時結合具體實例，驗證了算法中割點的判定條件以及回溯數組初始化的有效性和適用性。最后，給出了Tarjan算法在求解極大連通子圖過程中，結點和棧空間狀態轉化圖。

關鍵詞：極大連通子圖;雙連通分量;Tarjan算法

Abstract： Because the traditional naive algorithm takes too much time to solve the biconnected component of undirected graph， in order to find the biconnected component in linear time and obtain the maximally connected subgraph. The idea and implementation of Tarjan algorithm are analyzed in detail in this paper. At the same time， the validity and applicability of the decision condition of the cut point and the initialization of the backtracking array in the algorithm are verified by a concrete example. Finally， the state transition diagrams of node and stack space in the process of solving the maximally connected subgraphs of Tarjan algorithm are given.

Key words： Maximally Connected Subgraphs; Biconnected Component; Tarjan Algorithm

1 問題概述與分析

對于連通的無向圖（undirected graph），若刪除某個頂點或者某條邊，無向圖的連通性變得未知。如果只刪除無向圖中某條邊，無向圖的連通性和連通分量（connected component）發生改變，那么刪除的這條邊為無向圖的橋。若一個無向圖中不存在橋，這個無向圖為邊雙連通圖（edge-biconnected graph）。對于點雙連通圖，條件則更強一些。當頂點被刪除時，與頂點相鄰的邊也要被刪除。其中一個頂點被刪除后，無向圖的連通分量發生變化，該頂點為關節點（articulation vertex）。

在傳統樸素算法中，尋找無向圖中所有的橋和關節點需要多次DFS[1]（depth-first search）。一次DFS可以求出無向圖的連通分量，而每次DFS的漸近時間復雜度為[T（n）=O（N+E）]，其中[N]為無向圖的頂點數，[E]為無向圖的邊數。每次刪除無向圖中一條邊再進行DFS，即可求出刪除一條邊后的連通分量。同理可以得出，對頂點進行相同的若干次刪除操作，可求出無向圖中所有的關節點。而兩者的漸近時間復雜度分別為[O（E×（N+E））]， [O（N×（N+E））]，均為平方階。樸素算法求解無向圖的橋和關節點時間花費太高。應尋求一種新的算法，在線性時間內求出最優解。算法最理想的狀態是對無向圖DFS一次，可求出所有橋和關節點。此時的時間花費最低，時間復雜度[1]為[O（N+E）]。

Robert Endre Tarjan（美國計算機科學家、1986年圖靈獎得主）[2]提出了關于求解有向圖的強連通分量的Tarjan算法。考慮到無向圖是有向圖的特殊情形，當有向圖中相連的兩個點之間存在往返的路徑時，有向圖可轉化為無向圖。由此可以得出無向圖的線性Tarjan算法。本篇文章在有向圖的基礎上，引入了無向圖的回溯數組。通過圖形動態描述了DFS過程中low數組的更新情況，并對回溯過程中每個結點的low值更新進行了詳細的敘述。對于割點的判斷，從根節點和非根結點兩個維度出發，系統論證了割點的判斷依據。最后具體分析了在入棧和出棧操作中，每個雙連通分量對應的極大連通子圖的求解過程。

2 Tarjan算法的思想和基本理論

Tarjan算法采用DFS遍歷整個無向圖，通過對DFS搜索樹的分析和研究。引入了時間戳即深度優先數和用于記錄搜索樹中每個結點深度優先數的回溯數組。回溯數組記錄的深度優先數是該結點所能連接的最小的深度優先數。回溯數組是通過遞歸初始化，然后回溯更新的方式確定下來的。在遞歸訪問結點的過程中，將遍歷的結點依次入棧。回溯結點時，將棧中的元素循環出棧，直到遇到割點則跳出循環。而每次出棧的元素，剛好對應關節點的一個極大點連通子圖。為了使算法容易理解，本篇文章將父子結點對應的邊入棧。

2.1 無向圖的實例

為了后續算法的具體實現和問題討論的方便，這里不考慮獨立點和非連通圖。選定了0～6共7個頂點8條邊作為無向圖的研究對象，頂點之間的連接關系如下圖所示。

圖1展示了7個頂點8條邊的無向圖連接平面圖[3]。對圖1中的無向圖，從頂點0開始進行一次深度優先遍歷，得到相應的DFS遍歷樹。無向圖的搜索樹主要有兩種邊，頂點之間的實線為無向圖的樹邊（tree edge），虛線為無向圖的回邊（back edge）。每次訪問新的結點即父親結點到兒子節點的連接都會產生一條樹邊。回邊一方面為了表示已被訪問過的子孫結點與祖先結點的連接關系，另一方面將平面圖各個結點之間的連通關系體現出來。

2.2 無向圖的深度優先數