遍历两点之间所有路径问题

Question

老师你好，如果想遍历两点之间所有的路径，该怎么去解决呢，是不是需要将pre整形数组改为链表数组呢，需要用到广度优先遍历吗。

Answer 1

liuyubobobo 2019-09-04 13:56:54

1）

对，pre 应该存储所有的可能

2）

之后使用回溯法，找到所有从终止点到源点的可能

3）

这个算法是指数级别的，因为，在一张图中，两个点之间的所有路径的个数，就是指数级别的。要理解这一点，可以思考下面的图：

1 2 3

1   3   5   7  / \ / \ / \ / \ 0---2---4---6---8

这个图从源点 0 到终止点 8，一共有多少路径？答案是 2^4 = 16 条。

按照这个模式，再添加两个点，从 0 到 10，就有 32 条路径。

1 2 3

1   3   5   7   9  / \ / \ / \ / \ / \ 0---2---4---6---8---10

因为解是指数级的，算法至少是指数级的。

也正是因为这个原因，很少会有面试题目要求求出所有路径：）

继续加油！：）

• 提问者 hachiiiiiiiiiiii #1

  非常感谢！波波老师

• 慕姐5469507 #2

  老师，这个图的pre怎么存储所有可能，能说的再详细一点吗，感觉没有头绪。

• liuyubobobo 回复 慕姐5469507 #3

  现在我们的 pre[i] 只有一个空间，所以只有一个数字。但要存储所有可能，pre[i] 需要是一个 List，所有能到达 i 的节点 u，都应该放进 pre[i]。
  
  其实这样做，在寻找两点间所有路径的时候，意义不大，如果真的要求所有路径，完全可以直接进行回溯寻找所有路径。但是，这样做在找两点间的**所有最短路径**的时候很有意义（BFS 或者 Dijkstra 算法中）。不过一个图中两点间的最短路径的数量，也可能是指数级别的，所以通常也不会有问题要求求出两点间的所有最短路径的：）
  
  继续加油！：）

点开查看后面1条评论