algorithm - 查找方矩阵上两点之间的所有路径

Question

在标记为重复之前请仔细阅读!

我有一个矩阵:
0 0 0 x 0
0 0 0 0 0
0 0 0 0 0
0×0 0 0
0 0 0 0 0

你不能在矩阵中沿对角线移动!

我想找到两个“x”之间的所有可能路径。唯一的条件是，路径不能与自身交叉(因此没有循环)。显然 DSF 算法不会找到每条路径(要了解原因，请参阅本文:http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search)。

那么还应该使用什么算法呢？

Answer 1

没有访问集的 DFS 将找到图中的所有路径。

您必须维护一个特殊的访问集变体，它只与当前路径相关，而不是全局的。为此，每次“完成”探索一个顶点时，您都​​必须将其从集合中移除。

伪代码:

DFS(source,target,visited,path):
   if (source == target): //stop clause
       print path
       return
   for each son v of source:
      if v is in visited: //the vertex is already in the current path
           continue
      path.append(v)
      visited.add(v)
      DFS(v,target,visited,path)
      visited.remove(v)
      path.deleteLast()

此解决方案的复杂性呈指数级增长，但这是意料之中的，因为两个节点之间的简单路径数量呈指数级增长。