问查找特定起点和终点之间的所有可能路径

EN

您将希望通过Queue使用breadth-first search。

编辑：重读你的问题后，我认为问题在于你如何表示有向图，而不是你选择的算法。DFS或BFS都适用于您的情况，但您需要正确地实现该图，以便算法知道不要在错误的方向上尝试路径。

例如，

DFS查找0-1和1-3之间的路径，这对我来说是不可接受的。由于算法的本质，它会找到最短路径。根据规则，我要所有的可能性，而不仅仅是最短的。

实际上，BFS通常用于查找最短路径，而两者都可用于查找所有可能的路径。我会坚持使用DFS，因为它更容易实现(使用递归而不是Queue，等等)。

如果您正确地表示您的节点和规则，算法将不会找到不合法的路径。例如，如果你想从节点2开始，就让它成为开始节点。

最简单的方法是定义一个类来表示一个节点。在类中有一个包含这个“父”的所有“子”节点的数组列表。在节点中还有一个整数，它被用作深度优先遍历的“光标”。(也可以有另一个整数/字符字符串，即node #或其他标识符。)

将所有节点中的整数“光标”设置为零。选择你的开始节点--使它成为“当前节点”。在该节点上调用一个方法来遍历它。它拿起游标并提取相应的数组列表元素。然后，它为该数组列表元素中的节点调用"walk“方法。返回时，“游标”会递增。

当"walk“方法到达目标节点时，或者当"cursor”递增超过子数组的大小时，它就会返回。

在此过程中，您可以随心所欲地记录您想要的路径。一种方法是传递在每次"walk“调用中访问的节点的数组列表，在传递之前将当前节点添加到列表中。当遍历到达终端节点时，数组列表被复制为答案之一。从"walk“返回时，添加的元素将被删除。