5

私は昨日からこの問題で立ち往生しています。残念ながら/幸いなことに、この問題は私の非常に巨大な（私にとっては、C ++の初心者）アルゴリズムの約0.5％にすぎないため、適応して機能させることができる既存のコードのライブラリが必要です。

無向グラフのすべての円を検出して表示したいと思います。私のエッジは重み付けされていません。はい、私が本当に必要としているのは、すべてのサイクル、つまり、有向グラフのすべてのハミルトニアン サイクルのようなものです。

私はブースト グラフ ライブラリをいじっていましたが、DFS アルゴリズムは非常に有望に思えましたが、頂点を 1 回しか訪れないため、すべてのハミルトニアン サークルを与えることはできません。

現時点では、アルゴリズムの設計を続行できるように、コードが機能するだけで済みます。その後、パフォーマンスの問題を検討する可能性があります。5 ネストされた for ループを使用したソリューションも大歓迎です。

これは私がブーストから取得して遊んだコードですが、back_edgesの前任者を記録してアクセスする方法がわかりません。それが解決されたとしても、ブーストDFSは頂点を1回しか訪れません。

struct detect_loops : public boost::dfs_visitor<>
{
   template <class Edge, class Graph>
   void back_edge(Edge e, const Graph& g) {
      std::cout << source(e, g)
        << " -- "
        << target(e, g) << "\n";
   }
};

int main(int,char*[])
{
    typedef std::pair<int,int> Edge;
    std::vector<Edge> edges;
    edges.push_back(Edge(0,1));
    edges.push_back(Edge(1,2));
    edges.push_back(Edge(2,3));
    edges.push_back(Edge(3,1));
    edges.push_back(Edge(4,5));
    edges.push_back(Edge(5,0));
    edges.push_back(Edge(4,0));
    edges.push_back(Edge(5,6));
    edges.push_back(Edge(2,6));

    typedef adjacency_list<
       vecS, vecS, undirectedS, no_property,
       property<edge_color_t, default_color_type>
    > graph_t;
    typedef graph_traits<graph_t>::vertex_descriptor vertex_t;

    graph_t g(edges.begin(), edges.end(), 7);

    std::cout << "back edges:\n";
    detect_loops vis;
    undirected_dfs(g, root_vertex(vertex_t(0)).visitor(vis).edge_color_map(get(edge_color, g)));
    std::cout << std::endl;

    return 0;
}

上記の例では、通常は 3 サイクルしかないことを示していますが、4 つ以上のサイクルが予想されるため、1 つの頂点が複数のサイクルで表示される可能性があります。back_edge()そして第二に、ブーストがこのように私に与える3つのサイクルすべてにアクセスすることさえできませんstd::vector<uInt32> fCycle1, fCycle2,fCycle3. 私が得るのback_edge()は、ソースとターゲットの頂点だけです。

どんな助けやヒントにも感謝します。これまでのところ、ここにあるすべての例はサイクルまたはその数の存在を検出するだけで、存在するすべてのサイクルを一覧表示する方法を示したものはありません。

4

0 に答える 0