graph - 两个图节点之间的固定长度路径

Question

如果给定图上的两个节点，是否有一种算法可以在它们之间找到一条采用指定跳数的路由？任何节点都可以连接到任何其他节点。

目前的点位于二维空间中，所以我不确定图表是否是最好的方法。

Answer 1

您是否尝试过迭代深化 DFS？

Answer 2

如果您有节点正在寻求根据跳数查找路线，那么图表可能是正确的方法。不过，我不确定我是否了解您要做什么以及限制是什么，尤其是关于“任何节点都可以连接到任何其他节点”……这似乎有点开放。

然而，不管这一点；有一些图形表示：

似乎从第一个节点开始，然后从那里进行深度优先搜索，如果（a）所采取的跳数大于您指定的数字或（b）我们已经到达第二个节点，则终止搜索；这将确定在（最多）许多跳中连接两个节点的第一条（不仅是）路径。

如果它必须完全是指定的跃点，如果跃点已经结束，则终止搜索的任何分支，如果您也到达第二个节点，则成功终止。

Answer 3

愚蠢的方法：（数据结构是堆栈数组）。这基本上是对深度 N 进行广度优先搜索（BFS），除了如果允许循环（您没有澄清，但我认为它们是），您不会将访问的节点排除在进一步搜索之外。

1. 将起始节点推送到存储在数组中索引 0 处的堆栈上（索引 = 深度）

2. 对于每个级别/索引“l”0-N：

   对于存储在“l”级的堆栈上的每个节点，找到它的所有邻居，并将它们推送到存储在“l+1”级的堆栈上。

   重要提示：如果您的任务允许查找包含循环的路径，请不要检查您是否已经访问过您添加的任何节点。如果它不允许循环，请使用已访问节点的哈希，不要添加任何节点两次**

3. 当您结束“N-1”级时停止。

4. 循环遍历您刚刚添加到索引“N”处堆栈的所有节点并找到您的目标节点。如果找到：成功，如果没有，则无此路径。

请注意，如果通过“每个节点都可以连接”你暗示一个完全连接的图，那么存在一个不涉及实际访问节点的数学答案

（不过公式太长了，StackOverflow的text-entry字段里写不出来）