找到在特定开始和结束之间开始的所有可能路径 [英] Finding all possible paths starting between a specific start and end

问题描述

我想找到从特定节点开始到特定节点结束的所有可能路径。我在java中尝试了深度优先搜索，但它对我的情况并不起作用。因为我的路径将在同一个方向。我不想遍历所选节点周围的所有其他节点。

我无法上传显示我想要的图片。无论如何，我会尽力解释。
节点之间

0 1 2 3 4 5 6 7 8 9

我想要的路径例如，将从2开始到9，算法产生的可能路径应该是
2-7-9

2-4-6-8-9

2-4-6-9

对于节点1，我的下一个可能性只会是节点2，所以我不会尝试节点0和节点-3。由于我设置了一些特殊的规则，只有节点2适合节点1。节点2，节点4和节点7的下一个节点被选中。对于节点4，只有节点6是适合的。对于节点6，节点8和节点9是合适的。另一方面，对于node-7，下一个节点只有9个。

所有这些路径都被创建并保存在散列表或列表结构中。

DFS找到路径，例如，在0-1和1-3之间，这对我来说是不可接受的。由于算法的本质，它找到了最短的路径。我希望根据规则的所有可能性不是最短的。规则不是问题，所以我不想让你感到困惑和无聊。解决这个问题的一般方法对我来说很重要。

在此先感谢

解决方案

div>

如果您代表您的节点&规则正确，算法不会找到不合法的路径。例如，如果你想从节点2开始，就把它作为开始节点。最简单的是定义一个类来表示一个节点。在这个类中有这个父的所有子节点的数组列表。在节点中还有一个整数，用作深度优先行走的光标。 （不要伤害也有另一个整数/字符串是节点＃或其他标识符。）

将所有节点中的整数cursor设置为零。选择你的开始节点 - 使其成为当前节点。调用该节点上的方法来执行它。它拾取光标并提取相应的数组列表元素。然后它为该数组列表元素中的节点调用walk方法。

walk方法在到达目标节点时返回，或者当游标增加到超过孩子数组。

一路上，你保持任何你想要的路径记录。一种方法是传递每个walk呼叫访问的节点的数组列表，在传递它之前将当前节点添加到列表中。当步行到达终端节点时，数组列表被复制为其中一个答案。从步行返回时，添加的元素将被删除。

I want to find all possible paths starting from a specific node and ending at specific node. I tried depth first search in java but it did not work on my case. Because my paths will be on the same direction. I do not want to traverse all other nodes around selected ones.

I couldn't upload the image that shows what I want. Anyway, I'll try to explain. Among nodes

0 1 2 3 4 5 6 7 8 9

The paths I want to find are, for example, will start from 2 to 9. The possible paths produced by the algorithm should be

2-7-9

2-4-6-8-9

2-4-6-9

For node-1 my next possibility would be node-2 only, so I will not try node 0 and and node -3. Because of some special rules I set, only node-2 fits for node-1. Next nodes for node-2, node-4 and node-7 are selected. For node-4, only node-6 is suitable. For node-6, node 8 and node 9 are suitable. On the other hand, for node-7, the next node would be 9 only.

All these paths are created and saved in a hashmap or list structure.

DFS finds paths, for instance, between 0-1 and 1-3 which are unacceptable for me. Since the nature of the algorithm, it finds the shortest path. I want all possiblities according to the rule not the shortest one only. The rule is not the problem, so I do not want make you confused and bored. The general way to solve this problem is important for me.

Thanks in advance

解决方案

If you represent your nodes & rules properly, the algorithm would not be finding paths that aren't legit. Eg, if you want to start with node 2, make that the starting node.

Simplest is to define a class to represent a node. In the class have an array list of all the "child" nodes of this "parent". Also in the node have an integer that is used as a "cursor" for your depth-first walk. (Doesn't hurt to also have another integer/char string that is the node # or other identifier.)

Set the integer "cursor" in all nodes to zero. Pick your start node -- make it the "current node". Call a method on that node to walk it. It picks up the cursor and extracts the corresponding array list element. Then it calls the "walk" method for the node in that array list element. On return the "cursor" is incremented.

The "walk" method returns when it reaches the target node, or when the "cursor" is incremented beyond the size of the child array.

Along the way you keep whatever record of the path you want. One way is to pass an array list of the nodes visited on each "walk" call, adding the current node to the list before passing it along. When the walk gets to the terminal node the array list is copied as one of the answers. On return from "walk" the added element is removed.

这篇关于找到在特定开始和结束之间开始的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！