algorithm - 如何在图中找到精确长度的路径

Question

我想在无向图中找到固定长度的路径(在运行程序时给出)。我正在使用图形的邻接矩阵。
我尝试使用 DFS 或 A* 等算法，但它们只返回最短路径。

无法再次访问节点。

假设我的图有 9 个节点，最短路径是从 4 个节点构建的。
我想要一个额外的变量来“告诉”算法我想找到有 7 个节点的路径(例如)，它会返回包含在我预期路径 {1,2,4,5,6, 7,8}.
当然，如果没有我想要的路径解决方案，它不会返回任何内容(或者它会返回接近我的期望的路径，比方说 19 而不是 20)。

有人告诉我关于带回溯的 DFS，但我对此一无所知。
有人可以解释如何使用带回溯的 DFS 或推荐一些其他算法来解决该问题吗？

Answer 1

回溯看起来确实是一个合理的解决方案。这个想法是递归地找到所需长度的路径。

伪代码:

DFS(depth,v,path):
  if (depth == 0 && v is target): //stop clause for successful branch
       print path
       return
  if (depth == 0): //stop clause for non successful branch
       return
  for each vertex u such that (v,u) is an edge:
       path.append(v) //add the current vertex to the path
       DFS(depth-1,u,path) //recursively check all paths for of shorter depth
       path.removeLast() // clean up environment

上述算法将生成所有 所需深度的路径。
调用 DFS(depth,source,[])(其中 [] 是一个空列表)。

注意:

• 该算法将生成可能并不简单的路径。如果您只需要简单的路径 - 您还需要维护 visited 集，并在将每个顶点附加到找到的路径时添加每个顶点，并在从路径中删除它时将其删除。
• 如果您只想找到一条这样的路径 - 您应该从函数返回值(如果找到这样一条路径则为真)，并在返回值为真时中断循环(并返回真)。