BOBO老师，对于BFS求起始点到终点所有路径的问题一个疑问
来源：7-6 寻路
慕少1651928
2020-05-04
请教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老师 ：）
写回答
1回答
-
如果单从空间的角度，可以对于每个节点，记录一个 pre 值，即路径是从哪个节点过来的，如果在 bfs 的过程中，是从 a 遍历到 b 的，那么 pre[b] = a。如果要记录所有的路径，那么 pre[b] 就是一个数组，记录所有可以到达 b 的节点。最终我们可以从终点，通过 pre 的信息，一点一点反推出路径。
在我的图论算法课程中，对这个方法有详细讲解。有兴趣可以参考：https://coding.imooc.com/class/370.html
但是，从时间的角度，对于极端的测试用例，其实是不能忍受的。因为路径的个数可以是指数级别的（比如所有的点都是通路）。这个过程构成了一个从终点到起点的回溯算法。
继续加油！：）
032020-05-20
相似问题