BOBO老师，对于BFS求起始点到终点所有路径的问题一个疑问

Question

请教BOBO老师一个问题：

对于一个迷宫(0 表示通路，1表示障碍物):

S 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 1 0
1 1 1 1 1 E

对这样的迷宫至少存在下面两条路径
路径1:

S x x x x x
1 0 0 0 0 x
1 0 0 0 1 x
1 1 1 1 1 E

路径2:

S x x x x 0
1 0 0 0 x x
1 0 0 0 1 x
1 1 1 1 1 E

如果对于这样的迷宫求所有从S -> E的路径，对于所有的路径是否都需要保存一份visited的数组来存储已经走过路径呢，如果这样假如迷宫很大的话会非常消耗内存，这样的问题有什么好的解决方案吗？

提前感谢下BoBo老师 ：）

Answer 1

liuyubobobo 2020-05-04 16:57:33

如果单从空间的角度，可以对于每个节点，记录一个 pre 值，即路径是从哪个节点过来的，如果在 bfs 的过程中，是从 a 遍历到 b 的，那么 pre[b] = a。如果要记录所有的路径，那么 pre[b] 就是一个数组，记录所有可以到达 b 的节点。最终我们可以从终点，通过 pre 的信息，一点一点反推出路径。

在我的图论算法课程中，对这个方法有详细讲解。有兴趣可以参考：https://coding.imooc.com/class/370.html 

但是，从时间的角度，对于极端的测试用例，其实是不能忍受的。因为路径的个数可以是指数级别的（比如所有的点都是通路）。这个过程构成了一个从终点到起点的回溯算法。

继续加油！：）

• 提问者 慕少1651928 #1

  非常感谢！

• 提问者 慕少1651928 #2

  BoBo老师，这样解释的话是否说DFS比BFS可能更适合解决这类问题，这两天又想起了这个问题，有点久了，抱歉。

• liuyubobobo 回复 提问者 慕少1651928 #3

  看个人吧。dfs 回溯的过程也是指数级的。本质还是因为解空间本来就是指数级的。不过熟悉递归以后，通常递归算法写起来会更容易：）