BGL圖的簡單循環消除算法

Question

我的問題應該很簡單，給定一個圖（BGL adjacency_list）是否有一個簡單的算法來刪除循環？我的第一個嘗試是使用DFS訪問者來檢測將關閉該循環的邊緣，然後將其刪除，但我無法正確實施它。

有什麼建議嗎？代碼示例應該是最好的。

Answer 1

Boost很棒。它有一個depth_first_search接受訪問者的方法。 You can see more information about it here。

所有你需要做的就是實現這樣的訪問者：

class CycleTerminator : public boost::dfs_visitor<> { 
    template <class Edge, class Graph> 
    void back_edge(Edge e, Graph& g) { 
     //implement 
    } 
}; 

當然記住，後緣是關閉圖中的一個週期的邊緣。

Answer 2

這是一個簡單的DFS，正如你所說的。每次你來到一個你以前訪問過的節點時，都會有一個循環。只要刪除最後一個邊緣。

沒有特定語言的僞代碼。

void walk(current_node, previous_node) 
    if visited[current_node] 
     remove edge between current_node and previous_node 
     return 
    end 

    visited[current_node] = true 
    for (each adjacent node) 
     walk(adjacent_node, current_node) 
    end 
end