找到两个节点之间所有可能的路径在向标定图

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. 检查上面创建的集合和如果反向目的地等于你的来源，那么保留它，否则放弃（在你的情况下，没有东西可以丢弃）。 您已完成。