深度优先遍历（图的深度优先遍历）

深度优先遍历（Depth-First Search，简称DFS）是图论中一种常用的搜索算法，目的是遍历图中的所有节点。

## 1.简介

深度优先遍历是一种经典的图遍历算法，在探索图的连通性以及寻找路径等问题中具有广泛的应用。它的基本思想是从一个起始节点开始，不断沿着连接的边深入图中，直到无法继续前进为止，然后回溯到上一个节点，继续探索其他路径。深度优先遍历采用了「堆栈」的数据结构，通过递归或手动模拟堆栈操作来实现。

## 2.深度优先遍历的步骤

深度优先遍历的主要步骤如下：

### 2.1 访问起始节点

首先，选择一个起始节点作为遍历的起点。如果图中有多个连通分量，需要分别从每个连通分量的起始节点开始进行遍历。

### 2.2 标记节点为已访问

在访问一个节点之后，需要将其标记为已访问，以避免重复访问。

### 2.3 递归访问相邻节点

对于当前访问的节点，依次访问其相邻节点，并以这些相邻节点为起点进行递归访问。在递归访问时，需要考虑两个问题：

- 是否已经访问过该节点，防止陷入死循环；

- 是否已经到达最深的节点，即无法再进行后续探索。

### 2.4 返回上一个节点

当当前节点的所有相邻节点都被访问过后，需要返回上一个节点，继续遍历其未访问过的相邻节点。

### 2.5 重复步骤2-4，直到遍历完所有节点

根据以上步骤，可以使用递归或手动模拟堆栈的方式实现深度优先遍历。需要注意的是，由于图中可能存在回路，所以在实践中需要额外的标记来防止节点的重复访问。

## 3.实例说明

为了更好地理解深度优先遍历的过程，我们以一个无向图为例进行说明。假设有如下图所示的无向图：

```

A ---- B---- C

| |

| |

D----E D----F

```

其中，字母表示节点，连线表示节点间的连接关系。

以节点A为起始节点，开始进行深度优先遍历。按照步骤2.1，首先访问节点A，并标记其为已访问。然后按照步骤2.3，访问与节点A相邻且未访问过的节点，即节点B和节点D。

以节点B为起始节点，重复步骤2-4。访问节点B，并标记其为已访问。然后访问与节点B相邻且未访问过的节点，即节点A和节点C。

以节点C为起始节点，重复步骤2-4。访问节点C，并标记其为已访问。由于节点C没有邻接节点，按照步骤2.4，返回节点B。

回到节点B后，按照步骤2.4，返回节点A。

以节点A为起始节点，重复步骤2-4。访问节点D，并标记其为已访问。然后访问与节点D相邻且未访问过的节点，即节点B和节点E。

以节点E为起始节点，重复步骤2-4。访问节点E，并标记其为已访问。由于节点E没有邻接节点，按照步骤2.4，返回节点D。

...

按照以上步骤继续进行下去，直到所有节点都被访问过为止。

通过以上实例，我们可以清楚地看到深度优先遍历的过程，它的探索路径是沿着一条路径尽可能深入的。这种特点使得深度优先遍历在解决一些路径相关的问题时非常有效。

总结一下，深度优先遍历是一种重要的图遍历算法，通过不断沿着连接的边深入图中，从而探索所有节点。它的核心思想是利用递归或模拟堆栈的方式，访问节点，并继续遍历与节点相邻的未访问过的节点。深度优先遍历在解决图相关问题时具有重要的应用价值。