深度優先搜索算法

Question

在boost庫中實現的深度優先算法只訪問一次頂點。

是否有任何解決方法來停用此選項。我希望在任何頂點有分支時都可以訪問頂點。

任何建議...

編輯：圖爲無環的。

Answer 1

如果你想枚舉非循環圖中的所有路徑，那麼我認爲你不能輕易修改深度優先搜索來做到這一點。有專門爲此設計的算法，特別是：Rubin，F .; ，「Enumerating all simple paths in a graph」，Circuits and Systems，IEEE Transactions on，vol.25，no.8，pp.641-642，Aug 1978.

如果你知道Floyd-Warshall算法，可以很容易地修改它來計算矩陣中每個元素的路徑列表，而不是最小距離，這將完成這項工作。上面的文章使用了一些操作來使其運行速度更快一些。

Answer 2

希望頂點可以被訪問 每當有任何 頂點的分支。

你認爲迭代器在到達頂點分支時會做什麼？

深度優先搜索只是這個問題的答案之一。 Here是其他一些。

但是你必須選擇一些東西。這不是關閉DFS的問題。

Answer 3

我認爲這是不可能的設計。因爲如果你的圖形包含循環（並且你有它們，當你說，這個頂點可以被訪問多次），算法將以無限循環結束。