BGLグラフの単純なサイクル除去アルゴリズム

Question

私の問題は、グラフ（BGL adjacency_list）にサイクルを削除する簡単なアルゴリズムがあるので、非常に簡単なはずですか？私の最初の試みは、DFSビジターを使用して、サイクルを閉じるエッジを検出し、それを削除することでしたが、正しく実装できませんでした。

提案がありますか？コードサンプルが最適です。

Answer 1

ブーストが優れています。訪問者を受け入れる方法は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