2

隣接リストで表されるグラフがあります。これには depth_first_visit アルゴリズムを適用します。すべてがほぼ正常に動作します。問題は、アルゴリズムが開始点の頂点に接続されている頂点のみを訪問することです。個別の頂点 (接続なし) がある場合、それらはトラバースされません。もちろん、訪問されていない頂点を見つけて、それらからアルゴリズムを開始することでこの問題を解決しましたが、ドキュメントでは、これらの「分離された」頂点もトラバースする必要があると書かれています。質問 - 何か間違ったことをしていますか?

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge > GraphType;

vector<default_color_type> color_map(num_vertices(m_graph));

depth_first_visit(
       m_graph,
       *vp.first,
       custom_dfs_visitor(m_currentPath, visited),
       make_iterator_property_map(
           color_map.begin(),
           get(vertex_index, m_graph),
           color_map[0]),
       Terminator(m_currentPath)
    );
4

2 に答える 2

1

これは基本的にDFSが行うことであるため、アルゴリズムは正しいようです。接続されたすべてのノードをトラバースします。つまり、接続された各コンポーネントで個別に実行する必要があります。ユースケースによっては、ある種の DFS または BFS アルゴリズムを利用する、接続されたコンポーネントを見つけるためのアルゴリズムを調べたい場合があります。

于 2013-06-05T23:21:31.650 に答える
1

「グラフが切断されている場合、DFS はそのすべての頂点にアクセスしません。詳細については、接続されたコンポーネントのアルゴリズムを見つけるを参照してください。」参考：アルゴリスト

あなたは何も悪いことをしていません。そして、あなたの修正（他の未訪問のノードを見つけて、アルゴリズムを再度開始する）は、他の実装が行うことです。

さらに目に見える証拠として、TimL のページにあるこの優れた実装を見てください。クリックし続けると、DFS が実行されているのを見ることができます。(ページの真ん中までスクロールします。)

于 2013-06-05T23:15:21.723 に答える