两个图节点之间的固定长度路径
如果给定图上的两个节点，是否有一种算法可以找到它们之间经过指定跳数的路由？任何节点都可以连接到任何其他节点。
目前的点位于二维空间中，所以我不确定图表是否是最好的方法。
Is there an algorithm that will, if given two nodes on a graph, find a route between them that takes the specified number of hops? Any node can be connected to any other.
The points at the moment are located in 2D space, so I'm not sure if a graph is the best approach.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您是否尝试过迭代加深DFS？
Have you tried iterated-deepening DFS?
如果您的节点正在寻求根据跳数查找路由，那么图表可能是正确的方法。不过，我不确定我是否理解您想要做什么以及限制是什么，特别是关于“任何节点都可以连接到任何其他节点”..这似乎有点开放式。
然而，不管这一点；使用一些图形表示：
似乎从第一个节点开始，从那里进行深度优先搜索，如果（a）所采取的跳数大于您指定的数字或（b）我们已经到达第二个节点，则终止搜索节点;这将确定在（最多）那么多跳中连接两个节点的第一条（不仅仅是）路径。
如果它必须恰好是指定的跃点，则在跃点已超出的情况下终止搜索的任何分支，如果也到达第二个节点，则成功终止。
If you have nodes are seeking to find routes in terms of hops, then a graph is probably the right approach. I'm not sure I understand what you are trying to do and what the constraints are, though, especially with respect to "Any Node can be connected to any other" .. which seems a bit open ended.
Disregarding that, however; with some graph representation:
It seems like starting at the first node, and doing a depth first search from there, and terminating a search if (a) the hops taken is larger than your specified number or (b) we have arrived at the second node; this will determine the first (not only) path connecting the two nodes in (at most) that many hops.
If it has to be exactly the specified hops, terminate any branch of the search if the hops have gone over, and terminate with success if you have also arrived at the second node.
愚蠢的方法：（数据结构是堆栈数组）。这基本上是对深度 N 进行广度优先搜索（BFS），除了如果允许循环（您没有澄清，但我假设它们是），则不会从进一步搜索中排除访问过的节点。
将起始节点压入存储在数组中索引 0（索引=深度）的堆栈上
将
对于每个级别/索引“l”0-N：
对于存储在“l”层的堆栈上的每个节点，找到其所有邻居，并将它们推送到存储在“l+1”层的堆栈上。
重要提示：如果您的任务允许查找包含循环的路径，请不要检查您是否已经访问过您添加的任何节点。如果不允许循环，请使用已访问节点的哈希值来避免两次添加任何节点**
在结束级别“N-1”时停止。
循环遍历刚刚添加到索引“N”处堆栈的所有节点并找到目标节点。如果找到：成功，如果没有，则没有这样的路径。
请注意，如果“每个节点都可以连接”意味着一个完全连接的图，那么存在一个不涉及实际访问节点的数学答案
（但是，公式太长，无法写在StackOverflow 的文本输入字段）
Dumb approach: (data structure is array of stacks). This is basically doing Breadth First Search (BFS) to depth N, except that if loops are allowed (you did not clarify but I assume they are), you don't exclude the visited nodes from further searching.
Push starting node on a stack stored in the array at index 0 (index=depth)
For each level/index "l" 0-N:
For each node on a stack stored at level "l", find all its neighbors, and push them onto a stack stored in level "l+1".
Important: if your task allows finding paths that contain loops, do NOT check if you already visited any node you add. If it does not allow loops, use a hash of visited nodes to not add any node twice**
Stop when you end level "N-1".
Loop over all the nodes you just added to stack at index "N" and find your destination node. If found: success, if not, no such path.
Please note that if by "every node can be connected" you are implying a FULLY CONNECTED graph, then there exists a mathematical answer not involving actually visiting nodes
(however, the formula is too long to write in the text-entry field of StackOverflow)