如何找到在图形精确长度的路径(How to find path of exact length in

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

节点不能再次访问。

所以我们可以说，我的图表有9个节点和最短路径是从4个节点建。
我希望有更多的变量，它会“告诉”我想找到具有（例如）7个节点路径的算法，它将返回其包括在我的预期路径{1,2,4,5,6节点， 7,8}。
当然，如果对路径无解，我想，它会返回任何结果（或将关闭返回路径我expactations，假设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

上述算法将产生所需深度的所有路径。
invokation与DFS(depth,source,[])其中， []是一个空的列表）。

注意：

• 该算法将产生路径可能不会是简单的。 如果你只需要简单的路径-你还需要保持visited组，而当你把它添加到的路径添加每个顶点，并删除它，当你从路径中删除。
• 如果你想找到这样一个路径 - 你应该（如果这样的路径，发现真）从函数返回值，并打破循环（并返回true）时，返回值为true。

Answer 2:

为说明这个问题是NP完全问题。 哟可以平凡解决哈密顿环问题 ，给出一个有效的算法来解决你的问题。

因此，没有时间polynomnial溶液存在（除非P = NP）。 对于穷举搜索，指数时间的解决方案，检查@阿密特的回答。

Answer 3:

单个DFS应该是足够的：

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

这里，k是路径和路线[] []的长度的曲线图的邻接矩阵。 路径是一个全局变量。 这可以解释循环 - 它考虑到给定长度的所有路径。 从主，呼

path = 0;
dfs(source, k);
cout<<path;

需要注意的是节点的数量比跳数多一个。 还要注意的是，如果长度的路径是巨大的，这种功能可快速堆叠起来。 没有双关语意。

Answer 4:

尝试寻找最长路径，然后将其切割到需要的长度。 最长的路径也被称为图形的直径。 最长的路径可以通过运行DFS每个顶点被发现。

Answer 5:

假设你可以找到一个图的长度为d的路径，你可以运行该算法| V | 次，发现这是一个NP完全的最长路径。 所以，你可以试试下面的办法 -

1）近似算法2）强力方法（更适合的编程）。 使用GPU来加速你的代码。

此外，它可能是你的兴趣是 -

存在对的DAG的线性时间算法。

文章来源: How to find path of exact length in graph