深度优先遍历（DFS, Depth-First Search）

深度优先搜索（DFS）是一种用于遍历或搜索图/树的算法。其核心思想是：

尽可能深地搜索图的分支，当某个分支搜索完毕后，回溯到上一个分叉点，继续搜索其他未访问的分支。

直观理解

• DFS 就像走迷宫：一直往前走，遇到死胡同就退回到上一个分叉口，换一条路继续走。
• 使用栈（或递归调用栈）来记住回溯的位置。
• 对连通图只需调用一次 DFS；对非连通图需要对每个连通分量调用一次。

与 BFS 的对比

存储结构的影响

邻接矩阵实现 DFS：

• 查找某顶点的邻接点需要 $O(|V|)$ 时间
• 总时间复杂度 $O(|V|^2)$

邻接表实现 DFS：

• 查找某顶点的邻接点需要 $O(\deg(v))$ 时间
• 总时间复杂度 $O(|V| + |E|)$

邻接矩阵版 DFS

设图 G 的顶点集为 {v₁, v₂, ..., vₙ}：

1. 初始化 visited[] 数组，全部为 false
2. 选择起始顶点 vᵢ，执行 DFS_Visit(G, vᵢ)
3. 若还有未访问的顶点，选择下一个未访问顶点继续 DFS

DFS_Visit(G, v):
1. 访问 v，visited[v] = true
2. 对 v 的每个邻接点 w（按编号从小到大）：
   2.1 若 w 未被访问（visited[w] == false）：
       递归调用 DFS_Visit(G, w)

邻接表版 DFS

与邻接矩阵版类似，区别在于：
- 邻接矩阵：遍历 adjmatrix[v][0..n-1] 查找邻接点
- 邻接表：遍历 v 的邻接链表查找邻接点
- 邻接表中邻接点的顺序取决于建表时的插入顺序

DFS 序

DFS 过程中访问结点的顺序称为 DFS 序。同一个图，从不同起点开始或邻接点遍历顺序不同时，DFS 序可能不同。

DFS 生成树 / 生成森林

• 对连通图执行 DFS 会得到一棵 DFS 生成树。
• 对非连通图执行 DFS 会得到 DFS 生成森林。
• DFS 过程中，通过递归调用访问到的边组成树边（Tree Edge）。
• 其他边为回边（Back Edge）。

邻接矩阵版

#define MaxVertexNum 100

typedef struct {
    char vex[MaxVertexNum];                    // 顶点表
    int edge[MaxVertexNum][MaxVertexNum];      // 邻接矩阵
    int vexnum, arcnum;                        // 顶点数、边数
} MGraph;

bool visited[MaxVertexNum];                    // 访问标记数组

// 从顶点 v 出发，对图 G 进行 DFS
void DFS(MGraph G, int v) {
    visit(v);                   // 访问顶点 v
    visited[v] = true;          // 标记已访问
    for (int w = 0; w < G.vexnum; w++) {    // 遍历所有可能的邻接点
        if (G.edge[v][w] != 0 && !visited[w]) {  // 有边且未访问
            DFS(G, w);          // 递归访问
        }
    }
}

// 对整个图进行 DFS（处理非连通图）
void DFSTraverse(MGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;     // 初始化
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i])        // 从每个未访问的顶点开始
            DFS(G, i);
    }
}

邻接表版

// 邻接表结点定义
typedef struct ArcNode {
    int adjvex;                 // 该弧所指向的顶点位置
    struct ArcNode *nextarc;    // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    char data;                  // 顶点信息
    ArcNode *firstarc;          // 第一条弧
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;           // 邻接表
    int vexnum, arcnum;
} ALGraph;

// 邻接表版 DFS
void DFS_AL(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex])
            DFS_AL(G, p->adjvex);
        p = p->nextarc;
    }
}

非递归版（显式栈）

// 用显式栈实现 DFS（邻接矩阵）
void DFS_NonRecursive(MGraph G, int v) {
    int stack[MaxVertexNum], top = -1;
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;

    stack[++top] = v;
    visited[v] = true;
    visit(v);

    while (top != -1) {
        int cur = stack[top];
        bool found = false;
        for (int w = 0; w < G.vexnum; w++) {
            if (G.edge[cur][w] != 0 && !visited[w]) {
                stack[++top] = w;
                visited[w] = true;
                visit(w);
                found = true;
                break;           // 找到一个就深入，模拟递归
            }
        }
        if (!found)
            top--;              // 回溯
    }
}

给定无向图 G，顶点集 $V = \{0, 1, 2, 3, 4\}$，边集 $E = \{(0,1), (0,2), (1,3), (1,4), (2,3)\}$。

邻接矩阵：

    0  1  2  3  4
0 [ 0, 1, 1, 0, 0 ]
1 [ 1, 0, 0, 1, 1 ]
2 [ 1, 0, 0, 1, 0 ]
3 [ 0, 1, 1, 0, 0 ]
4 [ 0, 1, 0, 0, 0 ]

从顶点 0 开始 DFS（按编号从小到大访问邻接点）：

步骤 1: 访问 0，visited = {0}
步骤 2: 0 的邻接点 {1, 2}，选最小的 1
步骤 3: 访问 1，visited = {0, 1}
步骤 4: 1 的邻接点 {0, 3, 4}，0 已访问，选 3
步骤 5: 访问 3，visited = {0, 1, 3}
步骤 6: 3 的邻接点 {1, 2}，1 已访问，选 2
步骤 7: 访问 2，visited = {0, 1, 3, 2}
步骤 8: 2 的邻接点 {0, 3}，都已访问，回溯
步骤 9: 回溯到 3，回溯到 1
步骤 10: 1 的下一个邻接点 4
步骤 11: 访问 4，visited = {0, 1, 3, 2, 4}
步骤 12: 4 的邻接点 {1}，已访问，回溯
步骤 13: 回溯到 1，回溯到 0，所有顶点已访问

DFS 序：0 → 1 → 3 → 2 → 4
DFS 生成树的边：(0,1), (1,3), (3,2), (1,4)