如何找到图中精确长度的路径 [英] How to find path of exact length in graph

问题描述

我想找个固定长度的路径（假设在运行程序）的无向图。我用我的图的邻接矩阵。
我试图用一些算法，如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.

这篇关于如何找到图中精确长度的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！