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

Question

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

このオプションを無効にするための回避策はありますか？頂点にブランチがあるときはいつでも頂点にアクセスすることができます。

どんな提案...

EDIT：グラフが非環式です。

Answer 1

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

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

Answer 2

はどの 頂点に支店があるたびに頂点が を訪問することができることを望みます。

イテレータが頂点の枝に到達したときに、イテレータが行うことを提案していることはありますか？

深さの最初の検索は、この質問に1つのみ答えます。 Hereがあります。

しかし、何かを選択する必要があります。これはDFSを無効にする問題ではありません。

Answer 3

設計上不可能と思われます。グラフにサイクルが含まれている場合（そして、頂点に複数回訪問することがあるとすると、そこにはそのアルゴリズムがあります）、アルゴリズムは無限ループに終わるでしょう。