深度优先搜索（DFS）
沿着一条路尽量往深处走，走不下去再回到上一个岔路口，以此探索整个图。屏幕上的栈就是这条路。
- 时间 O(V + E)
- 内存 O(V)
- 使用栈
这些是什么意思？
- 顶点：图中的一个点，这里画成带字母的圆圈。
- 边：连接两个顶点的线。这里两个方向都能走。
- 邻居：通过一条边与某个顶点相连的顶点。按字母顺序查看。
- 队列：先进先出。BFS 总是取出等得最久的顶点。
- 栈：后进先出。DFS 总是从最后到达的顶点继续往下走。
- V 和 E：顶点数和边数。O(V + E) 表示每个顶点和每条边只被处理固定的次数。
0 / 60 步
- 在栈中
- 当前
- 已完成
- 搜索树的边
- 跳过的边
从 A 开始。点击播放，或一步一步查看搜索过程。
空格键：播放或暂停。左右方向键：单步移动。Home 和 End 键：跳转。
试试看： 选择有环的图。每条虚线边都通向一个已在栈中或已完成的顶点：这条边让一个环闭合。
工作原理
DFS 对第一个还没见过的邻居调用自身，再对那个顶点的第一个新邻居调用自身，依此类推。当一个顶点没有新邻居时，它的调用结束，DFS 退回一步，去试那里的下一个邻居。尚未结束的调用组成一个栈，它始终是从起点到当前顶点的路径。顶点旁边的数字是它被访问的顺序。
适用场合
想知道到底能到达哪些顶点、查找环、走迷宫，或给相互依赖的任务排顺序时，用 DFS。它找不到最短路径。