在無向圖中合併循環以創建樹

Question

問題：給定一個帶有循環的無向圖，合併最小數量的節點以消除循環。

例如，對於下面的圖解：

 G  H 
    /\ /\ 
A--B---C--D---E--F 
    \/  \ 
    I   J 

將

A--BCGI--DEH--F 
      \ 
      J 

我對如何做一個廣度優先搜索和合並來解決這個粗略的想法每當檢測到一個週期時都會向根發送節點，但看起來有點複雜。我想知道這個問題是否有一個衆所周知的算法。

順便說一句：這不是一個家庭作業。 :)

Answer 1

1. 創建一個生成樹使用BFS或DFS
2. 對於每一個邊緣，這不是在樹中，合併多達離他們最近的共同祖先的路徑邊的兩個節點，所有節點。

這聽起來很像你已經想到的:)。但是，如果您使用聯合查找數據結構來跟蹤合併，而不是實際修改圖形，那麼要容易得多。請參閱http://www.algorithmist.com/index.php/Union_Find