理想的算法在圖中發現的所有路徑

Question

讓我們這個圖例如：

現在讓我們說，我開始在頂點3，並希望找到頂點7 深度優先搜索（取決於實施情況）將首先看待兒童。現在，在我們的例子中，爲了論證，我從頂點2開始，然後到頂點4和頂點2，返回到頂點併到達頂點7，問題解決了。

我想要什麼：我想要得到所有可能的路徑，讓我從x到y（例如3到7：3,1,4,7 - 3,5,7 - 3， 4,7 - 3,5,6,9,7）。我沒有從Depth首次搜索中獲得。

你會建議什麼算法？

謝謝！

Answer 1

您應該使用修改後的BFS算法（http://en.wikipedia.org/wiki/Breadth-first_search）。在每個頂點上，你應該保存鄰居的列表，這些列表通向這個頂點（前輩），而不是隻有1個鄰居通向這個頂點。

當您想要從中找到所有路徑時，您只需從您的末端節點開始，並在每個頂點分支您的路徑，這些頂點具有多於一個的前導，並按照每個頂點中的前任創建的方式進行操作，直到獲得開始你擁有的所有分支節點。

編輯： 您可以使用DSF算法而不是BFS並以相同的方式對其進行修改。