將循環圖減少爲樹（依賴關係圖 - >樹）

我正在分析一些代碼的依賴關係。比方說，有一些交織的依賴，就像這樣：將循環圖減少爲樹（依賴關係圖 - >樹）

    F 
     A   /| 
     |  /| 
     |  /| 
     V  < V 
     B<--->C--->E 
     \ / | 
     > <  | 
     D<------+

B依賴於A和C ，c取決於B和F Ë取決於C和F d取決於B和C和E

我們對B和C有個問題，他們互相依賴。它們應該組合成一個超級節點。 C和E和F有問題，他們有一個循環。它們應該組合成一個超級節點。

你最終會與

A 
    | 
    V 
super 
node 
    | 
    | 
    D

是否有一個好的圖書館或算法源（Java者優先，但開放的建議），允許這樣的減少？

一個循環中的任何節點都組合成一個節點。指向新節點中任何節點的任何節點都應該指向新節點。新節點中任何節點指向的任何節點都應該使新節點指向該節點。

謝謝！

來源

2011-03-31 corsiKa

我相信你要求結合圖的strongly connected components。是？

我不記得算法，會試圖查找它。

編輯：我們學到的是Tarjan的。我不記得教得好，但是here is the Wikipedia page。

我會盡量給出基本的想法。爲每個節點指定一個索引＃。然後給每個節點一個低鏈路＃。低鏈接是來自我們的根節點的索引：要考慮的第一個可以找到我們路徑的節點。如果我們的低鏈接==我們的索引，那麼我們就是強連通組件的根。否則，我們與低鏈接處於同一組件。通過在整個圖上做這件事，我們可以確定哪些節點是強連接組件的一部分。

來源

2011-03-31 23:55:01 usul

事實上，這正是我正在尋找的。 Tarjan的算法看起來很簡單，足以實現我自己，但如果你有他們的Java實現，我會很樂意接受鏈接。 – corsiKa 2011-04-01 00:01:34

對不起，我沒有。我覺得像算法，因爲我知道它是有點不同於維基頁面，沒有堆棧...希望別人會擁有它？ – usul 2011-04-01 00:07:38

其實，維基百科有一個鏈接。當然，這是wiki，所以風險自負。祝你好運！ http://algowiki.net/wiki/index.php?title=Tarjan%27s_algorithm – usul 2011-04-01 00:08:40

將循環圖減少爲樹（依賴關係圖 - >樹）

回答

相關問題