数据结构与算法 - 05深度与广度优先搜索【非递归解法 与 打通墙问题】
- 深度优先搜索（Depth-First Search / DFS）
-
- 定义
-
-
- 从起点出发，选择一个方向不断地向前，直到无法继续，然后换一个方向，直到最后
-
-
- 应用
-
-
- 解决对上连通性问题。判断是否有一条路径从起点连接到终点
-
-
- 解题思路
-
-
- 使用 栈（Stack），后进先出 LIFO
-
-
- 练习
- 广度优先搜索（Breadth-First Search / BFS）
-
- 定义
-
-
- 从起点出发，一层一层地进行，每层当中的点距离起始点的步数上相同对，找到目的后结束
-
-
- 应用
-
-
- 解决最短路径的问题
-
-
- 解题思路
-
-
- 使用 队列（Queue），先进先出 FIFO
-
-
- 练习
-
-
- 社交中，两个人之间需要经过多少个朋友才能互相认识
- 假设从起始点 A 走到目的地 B 的过程中，求最短的路径的步数
-
-
-
- 假设从起始点 A 走到目的地 B 的过程中，最多允许打通 3 堵墙，求最短的路径的步数
-