c++ - 深さ優先探索アルゴリズム

Question

ブースト ライブラリに実装されている深さ優先アルゴリズムは、各頂点を 1 回だけ訪れます。

このオプションを無効にする回避策はありますか。頂点に分岐があるときはいつでも頂点にアクセスできるようにしたい。

なにか提案を...

編集:グラフは非循環的です。

Answer 1

非巡回グラフのすべてのパスを列挙したい場合、深さ優先検索を簡単に変更してそれを行うことはできないと思います。特に、この目的のために特別に設計されたアルゴリズムがあります。、「グラフ内のすべての単純なパスを列挙する」、Circuits and Systems、IEEE Transactions on 、vol.25、no.8、pp.641-642、1978 年 8 月。

Floyd-Warshall アルゴリズムを知っている場合は、それを簡単に変更して、最小距離ではなく、行列の各要素のパスのリストを計算することができます。上記の記事では、いくつかのビット操作を使用して、この実行を少し高速化しています。

Answer 2

頂点に分岐があるときはいつでも頂点にアクセスできるようにしたい。

イテレータが頂点の分岐に到達したときに何をすることを提案しますか?

深さ優先検索は、この質問への答えの 1 つにすぎません。 ここにいくつかの他のものがあります。

しかし、あなたは何かを選ばなければなりません。DFS をオフにすることは問題ではありません。

Answer 3

設計上無理だと思います。グラフにサイクルが含まれている場合 (頂点に複数回アクセスできると言うと、そこにサイクルがある場合)、アルゴリズムは無限ループに陥ります。