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

2018-06-22 15:09:37

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

节点不能再次访问。

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

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

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

伪代码：

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,[])调用DFS(depth,source,[]) （其中[]是一个空列表）。

注意：

该算法将生成可能不简单的路径。如果您只需要简单的路径 - 您还需要维护visited集，并在将每个顶点追加到找到的路径时添加每个顶点，并在将其从路径中移除时将其删除。

如果你只想找到一个这样的路径 - 你应该从函数返回值（如果找到这样的路径，则返回true），并在返回值为真时中断循环（并返回true）。

所述的问题是NP完全的。哟可以平凡解决哈密尔顿周期问题，给出一个有效的算法来解决你的问题。

因此，不存在多项式时间解（除非P = NP）。对于详尽的搜索，指数时间解决方案，请检查@ amit的答案。

单个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是路径的长度，routes [] []是图的邻接矩阵。路径是一个全局变量。这可以解释周期 - 它考虑给定长度的所有路径。从主，呼叫

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

请注意，节点数比跳数多一个。还要注意，如果路径长度很大，这个功能会很快堆积起来。没有双关语意。

链接地址: http://www.djcxy.com/p/63499.html

上一篇: How to find path of exact length in graph

下一篇: How to calculate the shortest path between two points in a grid