题
是否存在一种算法,如果在图表上给出两个节点,则会在它们之间找到一条路径,该路由需要指定的跳数?任何节点都可以连接到任何其他节点。
此刻的点位于2D空间,所以我不确定图表是否是最好的方法。
解决方案
如果您有节点正在寻找根据跳数查找路线,那么图表可能是正确的方法。我不确定我理解你要做什么以及约束是什么,特别是关于“任何节点可以连接到任何其他节点”。 ......似乎有点开放。
然而,无视这一点;用一些图表表示:似乎从第一个节点开始,从那里进行深度优先搜索,并在(a)所采用的跳数大于指定数量或(b)我们到达第二个节点时终止搜索;这将决定连接两个节点(最多)那么多跳的第一条(不仅是)路径。
如果它必须完全是指定的跃点,如果跳过了,则终止搜索的任何分支,如果你也到达了第二个节点,则终止成功。
其他提示
您是否尝试过迭代加深DFS ?
哑方法:(数据结构是堆栈数组)。这基本上是做广度优先搜索(BFS)到深度N,除了允许循环(你没有澄清,但我认为它们是),你不排除访问节点进一步搜索。
-
将存储在数组中的堆栈上的起始节点推送到索引0(索引=深度)
-
对于每个级别/索引“l” 0-N:
对于存储在级别“1”的堆栈上的每个节点,找到其所有邻居,并将它们推送到存储在级别“1 + 1”中的堆栈上。
重要提示:如果您的任务允许查找包含循环的路径,请不要检查您是否已访问过添加的任何节点。如果它不允许循环,请使用已访问节点的散列不要两次添加任何节点**
-
结束等级时停止“N-1”。
-
遍历您刚刚添加到索引“N”堆栈的所有节点。并找到您的目标节点。如果找到:成功,如果没有,没有这样的路径。
醇>
请注意,如果通过“每个节点都可以连接”你暗示一个完全连接的图,然后存在一个不涉及实际访问节点的数学答案
(但是,公式太长,无法在StackOverflow的文本输入字段中写入)