找到兩個節點之間所有可能的路徑在向標定圖

Question

可能重複：
Find the paths between two given nodes?

給定一個有向圖，如何找到兩個節點和回報之間的所有可能路徑那些路徑。

如果不是Java，請推薦我使用它的算法。我搜索了我發現的是使用BFS或DFS，但我無法看到我的情況更好。以及如何跟蹤所有路徑，不僅是最短路徑。

例如，給定下面的圖：

1 - > 2

1 - > 3

2 - > 3

3 - > 4

對於路徑在節點1和4之間，輸出應爲：

第一條路徑：1→2→3 - > 4

第二條路徑：1 - > 3 - > 4

Answer 1

對我來說，向後遍歷要容易得多。算法步驟如下：

1. 從目的地開始（即在您的示例中爲4）作爲起點。
2. 收集第二個元素作爲目的地的所有節點，例如（3,4）。
3. 假設起始點（第一次迭代中爲3）作爲新目標，並重復步驟1 & 2，直到沒有可用的匹配節點。 遞歸的好方案。你會得到你的收藏：[（1,2），（2,3），（3,4）]，[（1,3），（3,4）]
4. 檢查上面創建的集合和如果反向目的地等於你的來源，那麼保留它，否則放棄（在你的情況下，沒有東西可以丟棄）。 您已完成。