基于Tarjan算法的極大點(diǎn)連通子圖研究

付?？? 陳國(guó)軍 王文波

摘要：由于傳統(tǒng)樸素算法求解無(wú)向圖的雙連通分量時(shí)間花費(fèi)過(guò)高，為了在線性時(shí)間內(nèi)求出雙連通分量并得到極大連通子圖。文章對(duì)Tarjan算法的思想以及具體實(shí)現(xiàn)做出了詳細(xì)的分析。同時(shí)結(jié)合具體實(shí)例，驗(yàn)證了算法中割點(diǎn)的判定條件以及回溯數(shù)組初始化的有效性和適用性。最后，給出了Tarjan算法在求解極大連通子圖過(guò)程中，結(jié)點(diǎn)和?？臻g狀態(tài)轉(zhuǎn)化圖。

關(guān)鍵詞：極大連通子圖;雙連通分量;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 問(wèn)題概述與分析

對(duì)于連通的無(wú)向圖（undirected graph），若刪除某個(gè)頂點(diǎn)或者某條邊，無(wú)向圖的連通性變得未知。如果只刪除無(wú)向圖中某條邊，無(wú)向圖的連通性和連通分量（connected component）發(fā)生改變，那么刪除的這條邊為無(wú)向圖的橋。若一個(gè)無(wú)向圖中不存在橋，這個(gè)無(wú)向圖為邊雙連通圖（edge-biconnected graph）。對(duì)于點(diǎn)雙連通圖，條件則更強(qiáng)一些。當(dāng)頂點(diǎn)被刪除時(shí)，與頂點(diǎn)相鄰的邊也要被刪除。其中一個(gè)頂點(diǎn)被刪除后，無(wú)向圖的連通分量發(fā)生變化，該頂點(diǎn)為關(guān)節(jié)點(diǎn)（articulation vertex）。

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

Robert Endre Tarjan（美國(guó)計(jì)算機(jī)科學(xué)家、1986年圖靈獎(jiǎng)得主）[2]提出了關(guān)于求解有向圖的強(qiáng)連通分量的Tarjan算法。考慮到無(wú)向圖是有向圖的特殊情形，當(dāng)有向圖中相連的兩個(gè)點(diǎn)之間存在往返的路徑時(shí)，有向圖可轉(zhuǎn)化為無(wú)向圖。由此可以得出無(wú)向圖的線性Tarjan算法。本篇文章在有向圖的基礎(chǔ)上，引入了無(wú)向圖的回溯數(shù)組。通過(guò)圖形動(dòng)態(tài)描述了DFS過(guò)程中l(wèi)ow數(shù)組的更新情況，并對(duì)回溯過(guò)程中每個(gè)結(jié)點(diǎn)的low值更新進(jìn)行了詳細(xì)的敘述。對(duì)于割點(diǎn)的判斷，從根節(jié)點(diǎn)和非根結(jié)點(diǎn)兩個(gè)維度出發(fā)，系統(tǒng)論證了割點(diǎn)的判斷依據(jù)。最后具體分析了在入棧和出棧操作中，每個(gè)雙連通分量對(duì)應(yīng)的極大連通子圖的求解過(guò)程。

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

Tarjan算法采用DFS遍歷整個(gè)無(wú)向圖，通過(guò)對(duì)DFS搜索樹(shù)的分析和研究。引入了時(shí)間戳即深度優(yōu)先數(shù)和用于記錄搜索樹(shù)中每個(gè)結(jié)點(diǎn)深度優(yōu)先數(shù)的回溯數(shù)組?；厮輸?shù)組記錄的深度優(yōu)先數(shù)是該結(jié)點(diǎn)所能連接的最小的深度優(yōu)先數(shù)?；厮輸?shù)組是通過(guò)遞歸初始化，然后回溯更新的方式確定下來(lái)的。在遞歸訪問(wèn)結(jié)點(diǎn)的過(guò)程中，將遍歷的結(jié)點(diǎn)依次入棧?；厮萁Y(jié)點(diǎn)時(shí)，將棧中的元素循環(huán)出棧，直到遇到割點(diǎn)則跳出循環(huán)。而每次出棧的元素，剛好對(duì)應(yīng)關(guān)節(jié)點(diǎn)的一個(gè)極大點(diǎn)連通子圖。為了使算法容易理解，本篇文章將父子結(jié)點(diǎn)對(duì)應(yīng)的邊入棧。

2.1 無(wú)向圖的實(shí)例

為了后續(xù)算法的具體實(shí)現(xiàn)和問(wèn)題討論的方便，這里不考慮獨(dú)立點(diǎn)和非連通圖。選定了0～6共7個(gè)頂點(diǎn)8條邊作為無(wú)向圖的研究對(duì)象，頂點(diǎn)之間的連接關(guān)系如下圖所示。

圖1展示了7個(gè)頂點(diǎn)8條邊的無(wú)向圖連接平面圖[3]。對(duì)圖1中的無(wú)向圖，從頂點(diǎn)0開(kāi)始進(jìn)行一次深度優(yōu)先遍歷，得到相應(yīng)的DFS遍歷樹(shù)。無(wú)向圖的搜索樹(shù)主要有兩種邊，頂點(diǎn)之間的實(shí)線為無(wú)向圖的樹(shù)邊（tree edge），虛線為無(wú)向圖的回邊（back edge）。每次訪問(wèn)新的結(jié)點(diǎn)即父親結(jié)點(diǎn)到兒子節(jié)點(diǎn)的連接都會(huì)產(chǎn)生一條樹(shù)邊。回邊一方面為了表示已被訪問(wèn)過(guò)的子孫結(jié)點(diǎn)與祖先結(jié)點(diǎn)的連接關(guān)系，另一方面將平面圖各個(gè)結(jié)點(diǎn)之間的連通關(guān)系體現(xiàn)出來(lái)。

2.2 無(wú)向圖的深度優(yōu)先數(shù)