BFS？ - 找到所有從s到t最多有一定長度的路徑

Question

給定一個無向圖（連接）圖，我想要列表所有從s到t的路徑最多使用k邊緣。

一個幼稚的做法當然會，只取一BFS後從sk步驟（或DFS，我們以後k步驟切斷）停止，報告任何路徑在t結束。

我想知道是否有更復雜的方法來做到這一點？

Answer 1

我看不出你如何在這裏使用BFS或DFS。由於您需要枚舉s到t之間的所有可能路徑，因此如果不進行某些遞歸搜索，則無法解決此問題。此外，路徑數量通常在k之間將呈指數級增長，所以不希望任何重大的漸近複雜性改進。

在我看來，只有修剪可以稍微幫助你。 這裏有修剪值得一提的方式有兩種：

---

第一個是相遇中間人方法。

而是從頂點s在距離<= k搜索所有頂點，發現兩組頂點：從t從s在距離<= k/2，並在距離<= k/2。只需啓動兩個搜索（BFS或遞歸）來獲取它們。最後，合併結果：對於這兩個集合中的每個公共頂點v，從s到v以及從t到v（反轉）的路徑採取所有路徑對，並輸出聯合路徑。

上述的確切方法會多次列出一些路徑。爲了修復它，將每個特定長度的路徑存儲在單獨的列表中。然後分別合併每個長度的路徑。 請注意，如果您只想獲得簡單路徑（即無頂點重複），則MitM方法爲而不是適用。

---

第二種方法是使用距離估計，類似於A* search algorithm這樣做。假設你保證了從任何頂點v到目標頂點t的距離的下限。然後，如果從s到t確實無法繼續足夠短的完整路徑，則可以刪除從s到v的任何部分路徑。

Answer 2

這實際上並不是您需要的bfs，因爲要獲取所有路徑，必須保留已經訪問過的相鄰頂點。

具有以下圖：

• 0-> 1
• 0-> 0
• 1-> 1

所有的路徑從0到1包含2個步驟是[0,0,1]，[0,1,1]

天真的解決方案是保持在每個步驟（重複）的活動節點列表。要從幹i移到i + 1，請爲每個頂點創建一個包含所有相鄰頂點的新列表（不要刪除重複項）。