考研全科复习资料

408

数据结构

图的遍历（DFS/BFS）

一、定位信息

圈层：核心层（大纲考点）
前置知识：图的基本概念、图的存储（邻接矩阵/邻接表）、栈（DFS 递归调用栈）、队列（BFS）。
知识网络定位：图的遍历是所有图算法的基础操作，最小生成树（DS-05-04）、最短路径（DS-05-05）、拓扑排序（DS-05-06）等都建立在遍历思想之上。
考点热度：H级（高频重点） — 近 5 年真题中出现 ≥4 次，常以代码填空、算法设计题形式出现，单次分值可达 8–13 分。

二、知识点讲解

2.1 为什么需要遍历

图的遍历是从某个顶点出发，按照某种策略访问图中所有顶点，且每个顶点仅被访问一次。与树的遍历不同，图中可能存在回路，因此需要额外的"已访问标记"来避免重复访问。

2.2 深度优先搜索（DFS, Depth-First Search）

核心思想：从起始顶点出发，沿一条路径尽可能"深"地探索，直到无法继续时回溯，再探索下一条未走过的路径。

算法步骤（递归实现）：

访问起始顶点 $v$ ，标记 $v$ 为已访问。
找到 $v$ 的一个未被访问的邻接顶点 $w$ ，递归执行 DFS( $w$ )。
若 $v$ 的所有邻接顶点都已访问，则回溯到上一层。

伪代码（邻接矩阵存储）：

cpp

bool visited[MAX_VERTEX_NUM];  // 访问标记数组，初始全为 false

void DFS(MGraph G, int v) {
    // 从顶点 v 出发，对图 G 进行深度优先遍历
    visit(v);                  // 访问顶点 v
    visited[v] = true;         // 标记 v 为已访问
    for (int w = 0; w < G.vexnum; w++) {
        // 检查所有顶点，找 v 的邻接点
        if (G.arc[v][w] != 0 && !visited[w]) {
            // 若 w 是 v 的邻接点且未被访问
            DFS(G, w);         // 递归访问 w
        }
    }
}

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

时间复杂度：

邻接矩阵： $O(n^2)$ （每个顶点扫描一行）。
邻接表： $O(n + e)$ （遍历所有顶点和所有边表节点）。

2.3 广度优先搜索（BFS, Breadth-First Search）

核心思想：从起始顶点出发，先访问所有距离为 1 的邻接顶点，再访问所有距离为 2 的邻接顶点，依此类推。使用队列辅助。

算法步骤：

访问起始顶点 $v$ ，标记为已访问， $v$ 入队。
队列非空时，取出队首顶点 $u$ 。
找到 $u$ 的所有未被访问的邻接顶点，依次访问、标记、入队。
重复步骤 2–3，直到队列为空。

伪代码（邻接表存储）：

cpp

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

void BFS(ALGraph G, int v) {
    // 从顶点 v 出发，对图 G 进行广度优先遍历
    Queue Q;                   // 辅助队列
    InitQueue(Q);              // 初始化队列
    visit(v);                  // 访问起始顶点
    visited[v] = true;         // 标记为已访问
    EnQueue(Q, v);             // v 入队
    while (!IsEmpty(Q)) {
        DeQueue(Q, u);         // 取出队首顶点 u
        for (ArcNode *p = G.vertices[u].firstarc; p != NULL; p = p->nextarc) {
            int w = p->adjvex; // 获取邻接顶点下标
            if (!visited[w]) { // 若 w 未被访问
                visit(w);      // 访问 w
                visited[w] = true;  // 标记为已访问
                EnQueue(Q, w); // w 入队
            }
        }
    }
}

void BFSTraverse(ALGraph G) {
    // 对整个图进行 BFS（处理非连通图）
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;    // 初始化访问标记
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i])       // 若顶点 i 未被访问
            BFS(G, i);         // 从 i 开始一次 BFS
    }
}

时间复杂度：与 DFS 相同。

邻接矩阵： $O(n^2)$ 。
邻接表： $O(n + e)$ 。

2.4 遍历序列与生成树/森林

从一个顶点出发的 DFS 或 BFS 遍历过程中经过的边，构成一棵生成树（对连通图）或生成森林（对非连通图）。
DFS 生成树：按 DFS 访问顺序形成的树，体现"深度优先"特性。
BFS 生成树：按 BFS 访问顺序形成的树，体现"广度优先"特性。
同一个图，从同一顶点出发，DFS 生成树和 BFS 生成树可能不同。

2.5 图的连通性判断

从一个顶点出发进行 DFS/BFS，若能访问所有顶点，则图是连通的。
调用 DFS/BFS 的次数 = 连通分量数（无向图）或强连通分量数的初步判断（有向图需 Tarjan 等算法）。

三、记忆与理解辅助

技巧 1：DFS vs BFS 对比表

对比维度	DFS（深度优先）	BFS（广度优先）
数据结构	栈（递归调用栈）	队列
搜索策略	尽可能深，再回溯	逐层扩展
类比	走迷宫"一条路走到黑"	水波纹扩散
非递归实现	显式栈	队列
生成树特点	链状/深度大	宽度大/层次分明
最短路径	不保证（无权图）	无权图中保证最短

技巧 2：遍历序列唯一性判断

同一图 + 同一起点 + 同一存储结构 + 同一访问策略 → 遍历序列唯一。
改变存储结构（如邻接表中邻接点的链接顺序不同）→ 序列可能不同。
改变起点 → 序列通常不同。

技巧 3：口诀

"DFS 深到底，回溯找邻居"；"BFS 一层层，队列来帮忙"
"连通分量数 = 调用 DFS 的次数"

技巧 4：DFS/BFS 与树的遍历关系

对树做 DFS（先根）≈ 树的先序遍历
对树做 BFS ≈ 树的层序遍历

四、例题与精解

例题 1（基础巩固 — 完整遍历过程）

题目：对下图所示的无向图，从顶点 $A$ 出发，分别写出 DFS 和 BFS 的遍历序列。采用邻接表存储，邻接点按字母序排列。

【图示说明】无向图有 6 个顶点 $A, B, C, D, E, F$ 。边集： $(A,B), (A,C), (A,D), (B,E), (C,E), (D,F), (E,F)$ 。

命题意图：考查 DFS 和 BFS 遍历过程的完整执行。

审题分析：

已知：6 个顶点、7 条边的无向图，邻接表按字母序排列。
求解：DFS 序列和 BFS 序列。

解题思路：按照 DFS 和 BFS 的规则，逐步模拟执行过程。

完整步骤：

邻接表结构（按字母序）：

$A \to B \to C \to D$
$B \to A \to E$
$C \to A \to E$
$D \to A \to F$
$E \to B \to C \to F$
$F \to D \to E$

DFS 过程（从 $A$ 出发）：

访问 $A$ ，标记已访问。邻接点： $B, C, D$ 。
访问 $B$ （ $A$ 的第一个未访问邻接点），标记。 $B$ 的邻接点： $A$ (已访问), $E$ 。
访问 $E$ （ $B$ 的未访问邻接点），标记。 $E$ 的邻接点： $B$ (已访问), $C$ , $F$ 。
访问 $C$ （ $E$ 的未访问邻接点，字母序 $C$ 在 $F$ 前），标记。 $C$ 的邻接点： $A$ (已访问), $E$ (已访问)。无未访问邻接点，回溯到 $E$ 。
$E$ 还有未访问邻接点 $F$ 。访问 $F$ ，标记。 $F$ 的邻接点： $D$ , $E$ (已访问)。
访问 $D$ （ $F$ 的未访问邻接点），标记。 $D$ 的邻接点： $A$ (已访问), $F$ (已访问)。无未访问邻接点，逐层回溯。

DFS 序列： $A \to B \to E \to C \to F \to D$

BFS 过程（从 $A$ 出发）：

访问 $A$ ，入队。队列： $[A]$ 。
出队 $A$ 。 $A$ 的邻接点 $B, C, D$ 依次访问并入队。队列： $[B, C, D]$ 。
出队 $B$ 。 $B$ 的邻接点 $A$ (已访问), $E$ 。访问 $E$ ，入队。队列： $[C, D, E]$ 。
出队 $C$ 。 $C$ 的邻接点 $A$ (已访问), $E$ (已访问)。无新节点。队列： $[D, E]$ 。
出队 $D$ 。 $D$ 的邻接点 $A$ (已访问), $F$ 。访问 $F$ ，入队。队列： $[E, F]$ 。
出队 $E$ 。 $E$ 的邻接点 $B$ (已访问), $C$ (已访问), $F$ (已访问)。无新节点。队列： $[F]$ 。
出队 $F$ 。 $F$ 的邻接点 $D$ (已访问), $E$ (已访问)。无新节点。队列为空，结束。

BFS 序列： $A \to B \to C \to D \to E \to F$

方法反思：DFS 序列反映"深度"优先，先沿一条路走到底；BFS 序列反映"层次"，先访问所有直接邻居。注意：如果邻接点的链接顺序不同，DFS 序列会不同，但 BFS 序列在同一层内的顺序也可能不同。

例题 2（中等提升 — 连通分量与遍历）

题目：一个无向图有 10 个顶点，边集如下。编写算法求该图的连通分量个数，并给出每个连通分量的顶点集。

【图示说明】顶点 $v_0$ 到 $v_9$ ，边集： $(v_0,v_1), (v_0,v_2), (v_1,v_2), (v_3,v_4), (v_5,v_6), (v_5,v_7), (v_6,v_7), (v_8,v_9)$ 。

命题意图：考查利用 DFS/BFS 求连通分量的算法设计能力。

审题分析：

已知：10 个顶点的无向图及边集。
求解：连通分量个数及各分量的顶点集。

解题思路：对每个未访问的顶点执行 DFS/BFS，每次调用对应一个连通分量。

完整步骤：

算法伪代码：

cpp

void CountConnectedComponents(Graph G) {
    // 统计图 G 的连通分量个数
    int count = 0;              // 连通分量计数器
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;     // 初始化访问标记
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {      // 发现一个未访问顶点
            count++;            // 连通分量数加 1
            printf("连通分量 %d: ", count);
            DFS(G, i);          // 从该顶点开始 DFS，访问整个连通分量
            printf("\n");
        }
    }
    printf("连通分量总数: %d\n", count);
}

手动模拟：

从 $v_0$ 开始 DFS：访问 $v_0 \to v_1 \to v_2$ （ $v_2$ 的邻接点 $v_0, v_1$ 都已访问）。连通分量 1： $\{v_0, v_1, v_2\}$ 。
从 $v_3$ 开始 DFS：访问 $v_3 \to v_4$ 。连通分量 2： $\{v_3, v_4\}$ 。
从 $v_5$ 开始 DFS：访问 $v_5 \to v_6 \to v_7$ 。连通分量 3： $\{v_5, v_6, v_7\}$ 。
从 $v_8$ 开始 DFS：访问 $v_8 \to v_9$ 。连通分量 4： $\{v_8, v_9\}$ 。

结果：连通分量数 = 4。

方法反思：连通分量计数 = DFSTraverse/BFSTraverse 中调用 DFS/BFS 的次数。这个方法在实际考试中常与生成树结合考查。变式：如果是有向图，此方法统计的是从某顶点出发能到达的顶点集，不等于强连通分量。

五、考情分析

考查频次：近 5 年真题中出现 ≥4 次，是数据结构图部分的高频考点。
常见题型：选择题（判断遍历序列）、综合应用题（手写遍历过程、代码填空、算法设计）。
分值占比：选择题 2 分，综合题 8–13 分。
命题趋势：近年来更注重对遍历过程的完整理解和手写能力，而非简单记忆。DFS 和 BFS 的对比分析、连通分量求解、生成树构造是常见综合题考点。
基于大纲与命题规律推测

六、易错点提醒

错误表现：DFS 遍历过程中忘记标记已访问顶点，导致死循环。 错误原因：图中可能存在回路，如果不标记已访问顶点，会在回路中无限循环。 正确做法：在访问顶点的同时（不是之后）就将其标记为已访问。
错误表现：BFS 中误用栈代替队列。 错误原因：BFS 的核心是"先进先出"（FIFO），必须用队列。用栈会变成 DFS。 正确做法：BFS 用队列，DFS 用栈（或递归调用栈）。
错误表现：对非连通图只从一个顶点开始遍历，认为已访问所有顶点。 错误原因：非连通图中，从一个顶点出发只能访问其所在连通分量的顶点。 正确做法：外层循环遍历所有顶点，对未访问的顶点调用 DFS/BFS。
错误表现：认为 BFS 遍历序列一定唯一。 错误原因：当一个顶点有多个未访问邻接点时，访问顺序取决于存储结构中邻接点的排列顺序。 正确理解：遍历序列依赖于存储结构和邻接点的排列顺序，不保证唯一。

七、来源标注

依据 2026 考研统考大纲
依据《数据结构（C语言版）》严蔚敏版
依据大学本科经典教材共识

408 ​

数据结构 ​

图的遍历（DFS/BFS） ​

一、定位信息 ​

二、知识点讲解 ​

2.1 为什么需要遍历 ​

2.2 深度优先搜索（DFS, Depth-First Search） ​

2.3 广度优先搜索（BFS, Breadth-First Search） ​

2.4 遍历序列与生成树/森林 ​

2.5 图的连通性判断 ​

三、记忆与理解辅助 ​

四、例题与精解 ​

例题 1（基础巩固 — 完整遍历过程） ​

例题 2（中等提升 — 连通分量与遍历） ​

五、考情分析 ​

六、易错点提醒 ​

七、来源标注 ​

408