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

Question

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

无法再次访问节点.

因此,假设我的图表有9个节点,最短路径是从4个节点构建的.
我希望有一个额外的变量,它将"告诉"我想要找到具有7个节点的路径的算法(例如),并且它将返回包含在我的预期路径中的节点{1,2,4,5,6, 7,8}.
当然,如果没有我想要的路径解决方案,它将不返回任何东西(或者它会返回接近我的表达的路径,让我们说19而不是20).

有人告诉DFS有回溯,但我对此一无所知.
有人可以解释如何使用DFS与回溯或推荐一些其他算法来解决这个问题？

Answer 1

回溯确实似乎是一个合理的解决方案.想法是递归地找到所需长度的路径.

Psuedo代码:

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

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

注意:

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