Lecture 15: 图：概念、表示、DFS/BFS 与拓扑排序（Graphs: Concepts, Representations, Traversals & Topological Sort）（对应课程真实讲座 L25）

目录 · ← l14 · l16 →

Lecture 15: 图：概念、表示、DFS/BFS 与拓扑排序（Graphs: Concepts, Representations, Traversals & Topological Sort）（对应课程真实讲座 L25）

概述

链表与树之后，本讲迎来本季最“万金油”的数据结构——图（graph）：由顶点（vertex）与连接顶点的边（edge）构成，凡是“一堆东西之间存在两两关系”的问题几乎都能建模成图，如社交网络、路网、课程先修、网页链接。全讲覆盖三块：图的基本术语与“口味”（有向/无向、带权/无权、连通性）、三种表示法（邻接矩阵、邻接表、边表）的取舍，以及两种遍历（DFS、BFS）与只适用于有向无环图的拓扑排序（topological sort）。官方对应：L25（2026 年 8 月 5 日，周三，Graphs；本讲内容被官方列为期末考试重点，而 A6 之后没有图作业，主要靠练习与讲义）。

核心概念与算法原理

什么是图？ 图是“节点式（linked）结构”：一堆顶点 + 连接它们的边。它和链表、树同宗同源——链表可以看作“每条边只指向下一个节点”的特殊图，树是“无环、有单一根、边有层级方向”的特殊图。但图挣脱了两重束缚：图不一定只有一个入口（链表有头节点、树有根节点，图可以有很多起点）；图的关系不必有顺序或层级（可以不是 next/child 关系），而且可以有环（cycle）——这是树严格禁止的。顶点可以带编号，边可以带权重（weight，如距离、费用、耗时），可以带方向。

术语表（官方明确：期末考试可能直接考术语，务必熟记）：

• 路径（path）：一串顶点，相邻两个之间都有边相连；路径长度 = 经过的边数。
• 环/回路（cycle）：起点与终点相同的路径；自环（loop） 是一条从某顶点指向它自己的边。
• 相邻/邻居（adjacent/neighbor）：两个顶点之间有边。
• 可达（reachable）：存在从 A 到 B 的路径，则称 B 从 A 可达。
• 连通（connected）：无向图中任意两顶点互相可达；否则称不连通（disconnected）。有向图中“任意两顶点互相可达”则称强连通（strongly connected）。
• 完全图（complete graph）：任意两顶点之间都有边。
• 稠密（dense）与稀疏（sparse）：边的数量相对于可能的最大边数（n 个顶点最多约 n²/2 条无向边）而言是“很多”还是“很少”。
• 有向（directed）：边是单行箭头；无向（undirected）：边双向通行。
• 带权（weighted）：边上带数值；无权（unweighted）：只有“有没有边”。

三种表示法对比。设 n 为顶点数、E 为边数、deg(v) 为顶点 v 的度数（邻居个数）：

邻接矩阵还有个“对称浪费”：无向图的矩阵沿主对角线对称，每条边被存了两遍。官方的结论一句话：稀疏图用邻接表，稠密图用邻接矩阵；而遍历类算法（DFS/BFS/最短路径）几乎总在“列邻居”，所以邻接表是图算法的主场。官方课程自带 Stanford Graph 类（BasicGraph），本笔记一律用标准库自行实现同一思想。

最小生成树（MST）一句话带过：在带权无向图中找一棵连接全部顶点、总边权最小的树，经典算法有 Prim 与 Kruskal；官方说明本季不考，留作面试与 CS161 储备。

无权图最短路径一句话带过：BFS 天然给出无权图中“边数最少 / 换乘最少”的路径（逐层推进保证首次到达即最短）；而 DFS 只保证“若存在路径则能找到一条”，不保证最短（详细论证见 L26 之后的最短路径章节）。

深度优先搜索（DFS）。递归版逻辑极简：访问当前顶点并打上 visited 标记，然后依次对每个未访问的邻居递归深入——撞到死胡同就回溯。正是“一条道走到黑、撞墙再回头”。也可以用显式栈写成迭代版，效果等价。visited 标记不可或缺：图有环，不标记就会在环里无限打转。下图是示例图的 DFS 访问顺序（从 0 出发，按邻居顺序）：

DFS 访问序（数字是第几步）：
     0
    / \
   1   2        0(1) → 1(2) → 3(3) → 2(4) → 4(5) → 5(6)
   |   | \      输出: 0 1 3 2 4 5
   3 - 2  4
    \     |
     \    5

广度优先搜索（BFS）。用队列逐层扩散：先把起点入队并标记；每次出队一个顶点 u，把 u 的所有未访问邻居标记并入队。因为严格按“层”推进，第一次访问到某个顶点时的路径就是无权图最短路径。下图是同一张图的 BFS 分层示意（从 0 出发）：

第 0 层: 0
第 1 层: 1, 2        （0 的邻居）
第 2 层: 3, 4        （1、2 的邻居，且未访问）
第 3 层: 5           （3、4 的邻居）
BFS 输出: 0 1 2 3 4 5

拓扑排序（topological sort）。问题：有向图中，给所有顶点排一个线性顺序，要求“若有边 u→v（u 是 v 的前置/先修），u 必须排在 v 前面”。经典应用：课程表（边 = “x 是 y 的先修课”）、任务依赖（“先买面粉才能烤饼干”）、编译依赖。要点：

• 拓扑序不必是图中的一条路径——它只是把所有“箭头”整理成“一律朝右”的排列。
• 只有有向无环图（DAG）才有拓扑序：一旦有环（如 A 依赖 B、B 又依赖 A），就永远排不出谁先谁后。官方期末考试口径明确：有环 ⇔ 无拓扑序（两者互为充要）。
• 合法拓扑序通常不止一个（只要满足所有前置约束即可），Kahn 算法只输出其中某一个。
• 实现思路有二：Kahn 入度法（本讲代码采用）：不断挑出“入度为 0 = 无未满足前置”的顶点输出，并抹掉它发出的边（把邻居入度减 1），周而复始；若最终输出的顶点数少于总数，说明图中存在环。另一种是 DFS 完成序倒序：递归 DFS 记录每个顶点“访问完毕”的顺序，逆序即一个拓扑序（补充材料提及，本季不作要求）。

Kahn 过程示意（课程先修图：A 是 B、C 的先修，B、C 是 D 的先修，C 还是 E 的先修）：

初始入度: A:0  B:1  C:1  D:2  E:1
出队 A   → 输出 A，B、C 入度减 1 → 都变 0，入队
出队 B   → 输出 B，D 入度 2→1
出队 C   → 输出 C，D 入度 1→0、E 入度 1→0，D、E 入队
出队 D、E → 输出 D、E
拓扑序: A B C D E   （若图中存在环，队列会提前耗尽、输出不满 n 个）

代码示例与实现详解

示例 1：邻接表建图 + 递归 DFS + 队列 BFS。（用 vector<vector<int>> 直接当邻接表，顶点编号 0..n−1；如需带权或标签，可换成 struct Edge { int to; int weight; }; 的向量。）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 无权无向图：adj[u] 是 u 的所有邻居
struct Graph {
    int n;                       // 顶点数
    vector<vector<int>> adj;     // 邻接表
    explicit Graph(int vertices) : n(vertices), adj(vertices) {}

    void addUndirectedEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);     // 无向边 = 两条有向边
    }
};

// DFS（递归）：访问 u，再逐个深入未访问的邻居
void dfs(int u, const Graph& g, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : g.adj[u]) {
        if (!visited[v]) dfs(v, g, visited);
    }
}

// BFS（队列）：从 start 逐层扩散
void bfs(int start, const Graph& g) {
    vector<bool> visited(g.n, false);
    queue<int> q;
    visited[start] = true;       // 入队即标记，防止重复入队
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int v : g.adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    Graph g(6);
    g.addUndirectedEdge(0, 1);
    g.addUndirectedEdge(0, 2);
    g.addUndirectedEdge(1, 3);
    g.addUndirectedEdge(2, 3);
    g.addUndirectedEdge(2, 4);
    g.addUndirectedEdge(3, 5);
    g.addUndirectedEdge(4, 5);

    cout << "DFS 从 0 出发: ";
    vector<bool> visited(g.n, false);
    dfs(0, g, visited);
    cout << "\nBFS 从 0 出发: ";
    bfs(0, g);
    cout << "\n";
    return 0;
}

【代码做什么】 main 先搭出上节图示的 6 顶点无向图，然后分别从 0 出发跑 DFS 与 BFS。预期输出：DFS 打出 0 1 3 2 4 5，BFS 打出 0 1 2 3 4 5——同一张图、同一入口，两种策略给出截然不同的访问顺序，是体会“深度 vs 广度”的最佳实验。

【实现机制解说】 ① DFS 把“访问过”这一事实通过引用传递的 visited 传给所有递归分支共享，否则每个分支各持一份拷贝，标记等于白做；这是图版“传引用”的典型场景。② BFS 的标记时机是入队时而非出队时：若出队才标记，同一顶点可能被多个邻居重复入队，队列膨胀、甚至死循环。③ 想把 DFS 改成迭代版：把递归调用栈换成显式 std::stack，压栈前标记即可，访问顺序会略有不同但仍是合法 DFS。④ 若图不连通，单次 dfs/bfs 只能访问起点所在连通分量；外层再包一层“对所有未访问顶点依次启动遍历”就能覆盖全图。

示例 2：Kahn 拓扑排序（含环检测）。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 对 n 个顶点（0..n-1）的有向图做 Kahn 拓扑排序。
// 成功返回 true，order 装一个合法拓扑序；发现环返回 false。
bool topologicalSort(int n, const vector<vector<int>>& adj,
                     vector<int>& order) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) ++indegree[v];   // 统计每个顶点的入度

    queue<int> ready;                          // 入度为 0 = “前置全部满足”
    for (int u = 0; u < n; ++u)
        if (indegree[u] == 0) ready.push(u);

    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        order.push_back(u);
        for (int v : adj[u]) {                 // “解除”u 带来的一个前置约束
            if (--indegree[v] == 0) ready.push(v);
        }
    }
    return order.size() == n;                  // 输出不满 n 个 ⇔ 存在环
}

int main() {
    // 测试 1：DAG，边 A→B、A→C、B→D、C→D、C→E（顶点编号 A=0 … E=4）
    vector<vector<int>> g1(5);
    g1[0] = {1, 2};
    g1[1] = {3};
    g1[2] = {3, 4};
    vector<int> order1;
    cout << "测试1(DAG): "
         << (topologicalSort(5, g1, order1) ? "成功" : "失败(有环)") << " → ";
    for (int x : order1) cout << char('A' + x) << " ";
    cout << "\n";

    // 测试 2：加一条边 E→A，构成环 A→C→E→A，应检测失败
    vector<vector<int>> g2 = g1;
    g2[4].push_back(0);
    vector<int> order2;
    cout << "测试2(有环): "
         << (topologicalSort(5, g2, order2) ? "成功" : "失败(有环)") << "\n";
    return 0;
}

【代码做什么】 测试 1 的图正是核心概念里走查过的先修图，期望输出一个合法拓扑序（A B C D E 或 A C B D E 等，取决于队列顺序——注意这里显式展示了“合法拓扑序不唯一”）；测试 2 在 E 与 A 之间补一条反向边造出环 A→C→E→A，Kahn 结束后队列必然提前空掉，order.size() != n 触发失败分支，打印“失败(有环)”。

【实现机制解说】 ① 入度统计只需一遍全图扫描（O(n+E)）；“入度为 0”的含义是“所有指向我的前置都已被处理完”，这正是拓扑序要求的精确翻译。② 用队列装“就绪顶点”而不是数组，是因为队列入/出队都是 O(1)，且天然满足“谁先就绪谁先走”；换个容器（栈/优先队列）只会改变输出的具体顺序，不改变合法性。③ 环检测零成本：有环时环上每个顶点的入度永远减不到 0，队列耗尽后 order 缺员，比较 size 即可判定——官方 L25/L27 都强调“有环 ⇔ 无拓扑序”，此实现把判定落到了实处。④ 若把队列换成随机选点，就能随机生成一个合法拓扑序（官方练习之一）。

复杂度分析

设 n = 顶点数、E = 边数。对邻接表表示（示例代码采用）：

DFS/BFS 的 O(n+E) 来自“每个顶点至多标记一次、每条边至多被它的两个端点各遍历一次”；对稀疏图（E 远小于 n²）这比矩阵版的 O(n²) 划算得多——这也是图算法偏爱邻接表的原因。

关键要点

• 链表、树都是特殊图；图的自由在于多入口、无层级、可有环——遍历时必须用 visited 标记防死循环。
• 表示法按密度选：稀疏用邻接表（O(n+E) 空间、列邻居快），稠密用邻接矩阵（查边 O(1)），边表留给“按边处理”的算法。
• DFS 用递归（或显式栈）一探到底，适合判断连通性、找任意路径；BFS 用队列逐层扩散，无权图首次到达即最短（最少边/最少换乘）。
• 拓扑排序只对 DAG 有效，“有环 ⇔ 无拓扑序”；Kahn 法用入度表 + 队列，输出数不足 n 即判定有环。
• 术语（路径/环/连通/强连通/稠密/稀疏/带权/有向）与两种表示法的取舍是官方点名的期末考试范围。

常见陷阱与注意事项

• 遍历忘打 visited 标记：图有环时 DFS/BFS 无限递归或死循环。规避：入栈/入队/递归前先标记，且标记须在所有分支间共享（传引用）。
• BFS 在出队时才标记：同一顶点被多个邻居重复入队。规避：入队瞬间就标记。
• 对无向图跑 Kahn 拓扑排序：无向图每条边双向计数，几乎任何图都“有环”，结果无意义。规避：拓扑排序只用于有向图。
• DFS 求无权图最短路径：DFS 找到的只是“某一条”路径，不保证最短。规避：无权最短路径请用 BFS。
• 拓扑排序把结果直接当路径打印：拓扑序只是一般性排列，顶点之间未必相邻，别误读成一条通路。
• 邻接矩阵忘了无向图存两遍：只填上三角会导致查边不对称、遍历漏邻居。规避：要么存两遍，要么查询时按对称规则处理。
• 自环与平行边没想清楚：自环（u→u）在拓扑排序里直接构成环、在 BFS 里会让自己“已访问”而跳过，建模时要想清楚它们是否合法。
• 不连通图只遍历一次：从 0 出发的 DFS/BFS 覆盖不到另一分量。规避：需要全图遍历时外层循环启动所有未访问顶点。

思考题（带答案）

问题 1：给定任意一张无向图和一个起点，为什么 BFS 第一次“碰到”某顶点时经过的路径必然边数最少？ 答案：BFS 严格按层扩散：第 k 层的顶点必然是“经过恰好 k 条边、且首次可达”的顶点。若存在一条更短的边数为 m < k 的路径，该顶点应出现在第 m 层，矛盾。DFS 则可能顺着一条长路先到达，故不保证最短。

问题 2：为什么“有环 ⇔ 无拓扑序”？请用环上的顶点论证。 答案：若图中有环 u₁→u₂→…→uₖ→u₁，环上每个顶点都是“别人的前置”：u₁ 要求排在 uₖ 后面、uₖ 又要求排在 uₖ₋₁ 后面……传递下去形成 u₁ 必须排在 u₁ 后面的矛盾，任何线性顺序都无法满足。反之若无环（DAG），Kahn 算法总能不断找到入度为 0 的顶点并推进，最终排完所有顶点。

问题 3：邻接表与邻接矩阵在“检查 u、v 是否相邻”上的代价分别是多少？这对“边查询密集”的应用意味着什么？ 答案：邻接矩阵 O(1)（直接看 matrix[u][v]），邻接表需在 adj[u] 里线性找 v、代价 O(deg(u))。因此若算法主体是海量“任意两点是否相邻”查询（如部分动态规划），矩阵更合适；而 DFS/BFS/Dijkstra 这类“拿到一个点就扫它所有邻居”的算法，邻接表每步只花 O(deg)，整体 O(n+E)，是更优选择——这正对应官方“稠密图用矩阵、稀疏图用邻接表”的结论。