​【摘要】圖的演算法是進行靜態分析的基礎資料演算法，如何提高圖的分析效率，就需要對圖的演算法有進一步的認識。

1. 引言

在靜態分析技術中, 我們常用會將程式碼轉成抽象語法樹(AST), 然後採用深度遍歷（DFS）來完成對語法樹的遍歷和查詢，找到潛在的問題缺陷。

對於語義的分析，我們採用的控制流和資料流也都無一例外的採用了以圖為基礎的演算法, 透過圖的可達性, 來完成變數、表示式的可達分析, 以及變數的依賴分析、值流圖等等。

圖的演算法是進行靜態分析的基礎資料演算法，如何提高圖的分析效率，就需要對圖的演算法有進一步的認識。

1.1. 故事從1986年的圖靈獎說起

1986年的圖靈獎是John E.Hoperoft和Robert E·Tarjan兩人共同獲得， 而且Robert E·Tarjan曾是John E.Hoperoft的學生,他們的密切合作取得了演算法設計與分析方面的卓越貢獻, 贏得了1986年度美國計算機協會（Associationfor Computing Machinery, ACM）圖靈獎的榮譽。

1.2. 故事的前半段

在領獎的時候，John E.Hopcroft 做了一個“計算機科學:一門學科的出現” 的演講， 從他自己的經歷出發，展現了計算科學在那個風起雲湧的年代形成的過程。

那個時候，計算機科學的大部分課程的內容都是圍繞著數字計算機電路的設計以及如何減少構造這些電路所需要的電晶體數展開的。然而, 到了六十年代中期, 技術的進步已使得電晶體馬上就要被每片有多達幾百個元件的計算機晶片所取代。因此, 減少電晶體數再沒有麼意義，那時所謂的計算機科學的課程即將過時, 必須發展新的課程。

Hopcroft 並沒有接受過正規計算機教育，只是他在斯坦福大學讀電器工程學博士的時候，上過DavidHuffman（霍夫曼編碼的發明者）教的一門計算機課程，學習了開關電路、邏輯設計以及計算理論的基本知識。普林斯頓要Hoperoft在自動機理論方面開設一門新的課程，當時沒有任何教程可以參考, 只給了他推薦了6篇論文。 其中包括：

1943年,McCulloch和Pitts發表的一篇關於用來描述神經網路中活動的邏輯演算的論文。這些活動是一系列的電脈衝, 並能看作是0-1串。論文提出了一種描述神經網中的0-1串是如何結合以產生新的0-1串的方法。這種描述方法後來被髮展成為一種描述串集的正則表示式語言。數學家MichaelRabin和Dana Scott提出的一種具有有限量儲存其的計算機模型，這個模型就是有限狀態自動機。並證明了有限狀態自動機的可能的行為和正則表示式所描述的行為的一致性。 數學和計算機學思想的彙集，使計算機科學家相信正則語言和有限自動機的重要性。語言學家Chomsky研究發展的一種前後文無關文法的概念。這與Backus和Naur為描述各種程式設計語言的語法而發展的一套形式表示法驚人的等價。圖靈於1963年引入了一種簡單的計算裝置模型,現在稱做圖靈機。並論證了能夠進行的任何計算過程都能在圖靈機上程式設計序實現。圖靈機是現代可計算理論的基礎。數學家Hartmanis和Stearns採用演算法的執行步數來度量演算法的複雜性，並使這一方法發展了一種複雜性分類的理論。

1967年，Hopcroft轉去康奈爾大學，轉而研究演算法與資料結構。他相信理論計算機科學的方法學，可以用來為演算法設計發展一種科學基礎,這對於實踐者將是很有用的。

在七十年代初期, Hopcroft在斯坦福大學度過了一年的假期, 在那裡遇到Robert Tarjan並與他同用一間辦公室, Tarjan那時是二年級研究生。獲得這次圖靈獎的研究就是在那段合作時間裡作的。

Hopcroft 在發言的最後，還不忘呼籲，為了保持美國取得的技術和經濟的領導地位，必須對計算機科學進行全國性的投入和支援。

1.3. 故事的後半段

說到Tarjan，他在圖論演算法和資料結構領域有很大的貢獻。 下面對這個大牛也做個簡單的介紹。

Tarjan在1969年獲得了加州理工學院數學學士學位。在斯坦福大學，他獲得了他的計算機科學碩士學位（1971）和博士學位(1972). Tarjan從1985年開始任教於普林斯頓大學

Tarjan還擁有很多研究所和公司的工作經驗， 例如：AT&T貝爾實驗室、NEC研究所、InterTrustTechnologies、康柏、惠普、微軟等。

Tarjan是一個非常高產的計算機科學家，從計算機科學出版物線上參考網站dblp收集的有關他發表在的雜誌、會議和出版物，多達300+。

他獨立研究的演算法有：Tarjan離線的LCA演算法（一種優秀的求最近公共祖先的線性離線演算法）、Tarjan強連通分量演算法（甚至比後來才發表的Kosaraju演算法平均要快30%）、Hopcroft-Tarjan演算法（第一個平面性測試的線性演算法）。

下圖是他普林斯頓大學個人簡介中的一個插圖， 這個是他的另一個重要的研究領域：自適應搜尋樹的查詢(self-adjustingsearch tree)，在樹的遍歷過程中，改變樹的結構以提高樹的搜尋效率。

他的主要榮譽：

1986年，與JohnHopcroft分享了當年的圖靈獎，原因是對演算法和資料結構的設計分析做出的地基式的貢獻；1994年，被選為美國計算機協會（Associationfor Computing Machinery, ACM）院士；2004年，歐洲科學院的BlaisePascal數學和計算機科學獎章；1983年，RolfNevanlinna獎的第一個獲獎者，國際數學聯盟在資訊科學的數學方面的傑出貢獻而每四年獲獎一次；2. Tarjan演算法

圖的一些基本概念：

關聯（incident）：點為邊的端點;鄰接（adjacent）：點與點關聯同一條邊，或邊與邊關聯同一頂點；子圖：圖G'的點和邊都是圖G的子集，則G'為G的子圖;道路：從點v到點u的路徑；簡單道路：沒有重複邊的道路；迴路：起點與終點相同的道路；簡單迴路：沒有重複邊的迴路；連通：兩頂點間有道路；強連通：有向圖u→v與v→u都有道路；連通圖：任意兩頂點間都有道路（若有向圖除去方向後連通，則稱有向圖連通）；簡單圖：沒有重複邊和自環的圖；完全圖：任意兩頂點間有一條邊到達的簡單圖（有向完全圖與無向完全圖）；強連通（stronglyconnected）: 在有向圖G 中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通（stronglyconnected）；強連通圖: 如果有向圖G 的每兩個頂點都強連通，稱G 是一個強連通圖；強連通分量(stronglyconnected components): 非強連通圖有向圖的極大強連通子圖，稱為強連通分量(stronglyconnected components)。

求強連通分量就是我們今天要解決的問題，根據強連通分量定義，用雙向遍歷取交集的方法求強連通分量，時間複雜度為O（$N^2$+M）. 而Tarjan或Kosaraju演算法, 兩者的時間複雜度都是O（N+M）。

2.1. 演算法簡介

Tarjan 演算法是基於對圖深度優先搜尋的演算法，每個強連通分量為搜尋樹中的一棵子樹。搜尋時，把當前搜尋樹中未處理的節點加入一個堆疊，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。

定義:

o DFN(u)為節點u 搜尋的次序編號(時間戳);

o LOW(u)為u 或 u的子樹能夠追溯到的最早的棧中節點的次序號;

由定義可以得出，當 DFN(u)=LOW(u)時，以u為根的搜尋子樹上所有節點是一個強連通分量。

演算法：

1. 當首次搜尋到點u時DFN[u]=LOW[u]=time;

2. 每當搜尋到一個點，把該點壓入棧頂;

3. 當u和v有邊相連時:

3.1. 如果v不在棧中（樹枝邊），DFS(v)，並且LOW[u] =min{LOW(u),LOW(v)};

3.2. 如果v在棧中（前向邊/後向邊），此時LOW[u] =min{LOW[u],DFN[v]}

4. 當DFN[u]=LOW[u]時，將它以及在它之上的元素彈出棧，此時，彈出棧的結點構成一個強連通分量;

5. 繼續搜尋，知道圖被遍歷完畢。

由於在這個過程中每個點只被訪問一次，每條邊也只被訪問一次，所以Tarjan演算法的時間複雜度是O(n+m).

2.2. 演算法虛擬碼

2.3. 舉例演算

0.求下面有向圖的強連通分量

1. 從節點0開始DFS:

程式碼(1)-(5): 得到訪問鏈:0 -> 2 -> 4 -> 5, 把遍歷到的4個節點{0, 2, 4, 5}加入棧中; 四個節點的LOW[] 和 DFN[]值, 依次被Index標註成1到4; 注: 這裡也可以走另外一條路徑: 0 -> 2 -> 3-> 5;程式碼(9)-(13): 節點5的後續邊已經遍歷完成, 退出節點5時, 發現DFN[5] = LOW[5] = 4, 於是節點5出棧，{5}為一個強連通分量;

2. 返回節點4:

程式碼(6): LOW[4] =min(LOW[4], LOW[5]) = min(3, 4) = 3;程式碼(9)-(13): 節點4的後續邊已經遍歷完成, 退出節點4時, DFN[4] = LOW[4] = 3;退棧到節點4出棧，{4}為一個強連通分量;

3. 返回節點2:

程式碼(6): LOW[2]= min(LOW[2], LOW[4]) = min(2, 3) = 2;

4. 從節點2繼續搜尋到節點3:

程式碼(4)-(5): 繼續遍歷節點2的後續邊, 找到節點3;程式碼(1)-(2): 把3加入堆疊, Index = 5, DFN[3] =LOW[3] = 5;程式碼(3)-(8): 發現節點3向節點0有邊(3 -> 0)，且節點0在棧中，所以LOW[3] = min(LOW[3],DFN[0]) = min(5, 1) = 1；程式碼(3)-(8): 發現節點3向節點5有邊(3 -> 5), 但節點5已出棧;

5. 返回節點2;

程式碼(6): LOW[2] =min(LOW[2], LOW[3]) = min(2, 1) = 1;

6. 返回節點0;

程式碼(6): LOW[0]= min(LOW[0], LOW[2]) = min(1, 1) = 1;

7. 從節點0繼續搜尋到節點1;

程式碼(1)-(2): 把1加入堆疊, Index = 6, DFN[1] =LOW[1] = 6;程式碼(3)-(8): 發現節點1向節點3有邊(1 -> 3)，且節點3還在棧中，所以LOW[1] = min(LOW[1],DFN[3]) = min(6, 5) = 5;

8. 返回節點0;

程式碼(9)-(13): 退出時發現DFN[0] = LOW[0] = 1, 退棧到節點0出棧，組成一個連通分量{1, 3, 2, 0}。最終, 所有節點和邊都已經訪問到, 得到所有連通分量: {5}, {4}, {1, 3, 2,0}。列舉邊的時候, 與輸入順序相關, 可能計算順序不同, 但過程中每個點只被訪問一次，每條邊也只被訪問一次，所以總的結論一致.

2.4. Kosaraju演算法

Kosaraju是基於對有向圖及其逆圖兩次DFS的方法，其時間複雜度也是 O(N+M)。與Trajan演算法相比，Kosaraju演算法可能會稍微更直觀一些。但是Tarjan只用對原圖進行一次DFS，不用建立逆圖，更簡潔。

在實際的測試中，Tarjan演算法的執行效率也比Kosaraju演算法高30%左右。

3. Tarjan演算法實現

為了便於後期的擴充套件, 適用更為廣泛的圖運算。 這裡演算法的實現中，圖的表示採用了Googleguava庫中的common.graph,你需要在pom.xml 中加入guava的依賴包如下:

為了和舉例中圖的特徵保持一致, 圖結構採用guava裡的MutableGraph graph,Integer的值表示結點的編號。 例如 graph.putEdge(0, 2); 表示增加一條有向邊, 從結點0 指向 結點2, graph 會判斷結點0 和2 是否存在結點中存在, 如不存在, 則會增加相應的結點。

大家可以根據自己的需要採用不同的圖結構。

目前我們常用的圖基礎資料結構:

o JUNG:2016.9.8 - 2.1.1. 據說作者正在打算採用google 的guava 重寫這個工程;

o JGraphT:2020.6.15 - 1.5.0. 這個是目前很活躍的一個圖基礎資料包, 裡面也實現Tarjan演算法, 後面有時間去看下具體的實現。 Maven依賴的引用如下:

3.1. 演算法程式碼

3.2. 驗證程式碼

驗證程式碼使用junit完成結果的驗證。生成可變圖graph裡面的:incidentEdgeOrder(ElementOrder.stable()), 是為了保證關聯邊的讀取時和輸入的順序一致, 以便得到和前面演算過程的一致性的結果.

4. 結論計算機科學是一個綜合性的學科;基礎科學的研究論文的重要性, 不僅在於其技術方面的貢獻, 更重要的是它們提供一種概念上的見解或者一種研究範例；基礎科學對一個國家很重要；計算機科學對一個國家很重要。5. 參考

1. JohnE.Hoperoft 簡介

2. 1986年圖靈獎John E.Hoperoft發言：COMPUTER SCIENCE: THEEMERGENCE OF A DISCIPLINE

3. RobertEndre Tarjan 簡介

4. dblp -Robert Endre Tarjan

5. Depth-FirstSearch and Linear Graph Algorithms

6. Guava Grpah