遍历两点之间所有路径问题
来源：5-10 BFS 和 DFS 的神奇联系，与本章小结
hachiiiiiiiiiiii
2019-09-04
老师你好，如果想遍历两点之间所有的路径，该怎么去解决呢，是不是需要将pre整形数组改为链表数组呢，需要用到广度优先遍历吗。
写回答
1回答
-
1）
对，pre 应该存储所有的可能
2）
之后使用回溯法，找到所有从终止点到源点的可能
3）
这个算法是指数级别的，因为，在一张图中，两个点之间的所有路径的个数，就是指数级别的。要理解这一点，可以思考下面的图：
1 3 5 7 / \ / \ / \ / \ 0---2---4---6---8
这个图从源点 0 到终止点 8，一共有多少路径？答案是 2^4 = 16 条。
按照这个模式，再添加两个点，从 0 到 10，就有 32 条路径。
1 3 5 7 9 / \ / \ / \ / \ / \ 0---2---4---6---8---10
因为解是指数级的，算法至少是指数级的。
也正是因为这个原因，很少会有面试题目要求求出所有路径：）
继续加油！：）
342021-09-18
相似问题
单源路径问题
回答 1
图后序遍历与前序遍历
回答 1