我想找个固定长度的路径（假设在运行程序）的无向图。我用我的图的邻接矩阵。 我试图用一些算法，如DFS或A *，但他们只返回的最短路径。

I would like to find path of fixed length (given while running the program) in undirected graph. I'm using adjacency matrix of my graph. I tried to use some algorithms like DFS or A*, but they only return the shortest path.

节点不能再次访问。

所以我们可以说，我的图有9个节点的最短路径是由4个节点建设。 我想有一个会告诉我想找到路径，具有（例如）7个节点的算法额外的变量，它将返回其包括在我的预期路径{1,2,4,5,6节点， 7,8}。 当然，如果有，我想对路径无解，它会返回任何结果（或将关闭返回路径，我expactations，假设19，而不是20）。

So let's say that my graph have 9 nodes and the shortest path is built from 4 nodes. I want to have additional variable that will "tell" the algorithm that I want to find path which have 7 nodes (for example) and it will return nodes which are included in my expected path {1,2,4,5,6,7,8}. Of course, if there is no solution for path that I want, it will return nothing (or it will return path close to my expactations, let's say 19 instead of 20).

有人说是有关DFS与回溯，但我不知道这件事。 有人能解释如何使用DFS与回溯或推荐一些其他的算法来解决这个问题？

Someone told be about DFS with backtracking, but I don't know anything about it. Could someone explain how to use DFS with backtracking or recommend some other algorithms to solve that problem?

推荐答案

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

Backtracking indeed seems like a reasonable solution. The idea is to recursively find a path of the required length.

的伪code：

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与 DFS（深度，来源，[]）（其中 [] 是一个空表）。

The above algorithm will generate all paths of required depth. invokation with DFS(depth,source,[]) (where [] is an empty list).

请注意：

该算法将生成可能不是简单的路径。如果你只需要简单的路径 - 你还需要保持访问设定，当您将追加其添加每个顶点找到的路径，并删除它，当你将其删除路径。 如果你想找到这样一个路径 - 你应该（如果这样的路径，发现真）从函数返回值，并打破循环（返回true）时，返回值为true The algorithm will generate paths that might not be simple. If you need only simple paths - you also need to maintain visited set, and add each vertex when you append it to the found path, and remove it when you remove it from the path. If you want to find only one such path - you should return value from the function, (true if such a path was found), and break the loop (and return true) when the return value is true.