视频字幕
深度优先搜索，简称DFS，是一种用于遍历或搜索树或图的算法。它的核心思想是尽可能深地探索图的分支。当一个节点被访问后，DFS会沿着一条路径一直向下探索，直到到达叶子节点或无法继续前进。然后，它会回溯到上一个节点，继续探索其他未被访问的分支。在这个例子中，DFS的遍历顺序是A、B、D、E、C、F。
深度优先搜索有两种主要的实现方式。第一种是递归实现，它利用函数调用栈隐式地实现回溯。当我们访问一个节点后，我们递归地访问它的所有未访问的邻居。第二种是迭代实现，它使用一个显式的栈来存储待访问的节点。我们从栈中弹出一个节点，访问它，然后将它的所有未访问的邻居压入栈中。这两种实现方式在功能上是等价的，但在某些情况下，由于递归深度限制，迭代实现可能更为实用。
让我们通过一个迷宫问题来演示深度优先搜索的执行过程。在这个迷宫中，我们从绿色起点开始，目标是到达红色终点。DFS的执行过程包括四个步骤：首先，选择起始节点并标记为已访问；其次，访问该节点；然后，对于当前节点的每个未访问的邻居，递归执行DFS；最后，如果所有邻居都已访问，则回溯到上一个节点。在这个例子中，DFS会先尝试一条路径，如果遇到死胡同，就会回溯并尝试其他路径，直到找到终点或探索完所有可能的路径。
深度优先搜索有许多重要的应用场景。首先，它可以用来查找图中的路径，比如从一个节点到另一个节点的路径。其次，它可以判断图是否连通，即是否存在一条路径连接任意两个节点。第三，DFS可以用于拓扑排序，这在处理依赖关系时非常有用，比如课程的先修关系。在这个例子中，我们有一个课程依赖关系图，箭头表示先修关系。使用DFS进行拓扑排序，我们可以得到一个合理的学习顺序，确保在学习某门课程之前，已经学习了它的所有先修课程。此外，DFS还可以用于查找图的强连通分量，以及解决迷宫和谜题问题。
最后，让我们比较一下深度优先搜索（DFS）和广度优先搜索（BFS）的区别。首先，在搜索策略上，DFS尽可能深地探索图的分支，而BFS则是逐层探索。其次，在数据结构上，DFS使用栈（无论是递归调用栈还是显式栈），而BFS使用队列。第三，在路径特性上，DFS不保证找到的路径是最短的，而BFS保证找到的路径是最短的。最后，在空间复杂度上，DFS的空间复杂度与图的深度成正比，而BFS的空间复杂度与图的宽度成正比。在图中，我们可以看到DFS和BFS的遍历顺序是不同的。DFS会先一直向下探索，直到无法继续，然后回溯；而BFS会先访问所有邻近节点，然后再向下一层扩展。