Sherfiter's wiki for fun

第 6 章 · 图

前几章的结构都是「规矩的」:线性表排成队,树是分层的。图把最后一条限制也撤了:任何东西和任何东西都可以有关系。城市间的高速公路、社交网络的好友关系、编译器的模块依赖、操作系统的进程等待图(操作系统课第 5 章的死锁检测就是在图上找环),全是图。图论算法多而杂,本章的主线只有两条:遍历(DFS/BFS,一切的起点)和最优化(最小生成树、最短路径,贪心思想的高光时刻)。先从一个真实的建模问题开始。

6.1 存图:选结构就是选命

要给「校园导航」建模:路口是顶点,道路是带长度(权)的边。第一个决定是存法,它直接决定后面每个算法的性能:

邻接矩阵:V×V 的二维数组,g[u][v] 存边权(无边存无穷)。判断「u 到 v 有没有路」O(1),但空间 O(V²),10000 个路口的地图就是 10⁸ 格,九成九是无穷。邻接表:每个顶点挂一条出边链表(第 2 章的链表),空间 O(V+E),遍历 u 的邻居只走 u 自己的链;代价是判边要扫链表 O(deg)。

typedef struct Edge { int to, w; struct Edge *next; } Edge;
Edge *adj[MAXV];          // adj[u]: u 的出边链表头
void add_edge(int u, int v, int w) {
    Edge *e = malloc(sizeof *e);
    e->to = v; e->w = w; e->next = adj[u];
    adj[u] = e;                             // 头插,O(1)
}

选法口诀按密度分:稀疏图(真实世界绝大多数,边数和顶点同量级)用邻接表;稠密图、需要频繁判边、或要用 Floyd 这类矩阵型算法时用邻接矩阵。第 11 章的并查集、第 12 章的内存视角会回到这张结构对照表。

6.2 DFS 与 BFS:两种走法,两种世界

DFS(深度优先):沿着一条路走到黑,走不动了回溯换岔路。递归实现三行:

int visited[MAXV];
void dfs(int u) {
    visited[u] = 1;
    for (Edge *e = adj[u]; e; e = e->next)
        if (!visited[e->to]) dfs(e->to);
}

BFS(广度优先):逐层扩散,第 3 章的队列直接上场:起点入队,出队时把未访问邻居入队。两者都 O(V+E)(每顶点每边各经过一次),但「形状」完全不同,这个差异就是它们各自的饭碗:

  • BFS 的扩散像水面波纹:第一次到达某点时的层数,就是起点到它的最少步数。无权最短路、社交网络的「几度好友」,靠它。DFS 走到某点的路径深度毫无「最短」含义(它只是先走的那条岔路)。
  • DFS 的形状是一条深入回溯的路径,天然适配「探完一个分支再下一个」的语义:迷宫找任意出路、拓扑排序、检测环、强连通分量,全是 DFS 的地盘。

一个工程细节:递归 DFS 在深图(比如 10 万个节点串成一条链)会爆栈(栈帧是有限的,操作系统课第 2 章),生产实现要改成显式栈的迭代版,这正是第 3 章「栈」的又一用武之地。

6.3 最小生成树:铺光缆问题

n 个村庄,村间候选道路各有造价,要让所有村连通且总造价最小——选出的 n-1 条边就是最小生成树(MST)。两种贪心,贪的东西不同:

Kruskal(从边下手):所有边按权排序,从小到大尝试,只要不形成环就收入,收满 n-1 条为止。「判环」靠并查集(第 11 章):一条边两端已在同一集合,加入必成环。O(E log E),稀疏图首选。

Prim(从点下手):任选起点,反复把「离已连区域最近的未连点」拉进来,「找最近」用第 5 章的堆,O(E log V),稠密图顺手。

两者的贪心正确性都靠「切分定理」背书(任何横切图的最轻边必在某棵 MST 里),第一次理解这个证明是图论入门的高光时刻,建议拿一条具体图亲手验证。真实投影:电网规划、网络布线、聚类分析的层次聚类,全是 MST 变装。

6.4 最短路径:Dijkstra 与 Floyd 的分工

导航的核心问题。Dijkstra 管单源(一个起点到所有点),贪心策略和 Prim 神似:每次把「当前距离最小的未确定点」敲定为终点,再松弛它的邻居:

dist[] 全设 ∞,dist[源] = 0
反复:取未确定点中 dist 最小的 u(堆,第 5 章)
     对 u 的每条边 (u,v,w):若 dist[u]+w < dist[v],更新 dist[v]

O(E log V)。它有个必须刻在脑子里的前提:边权非负。贪心「敲定就不改」的正确性依赖「路越走越长」,负权边会打破它(走了负边回头更便宜),那时换 Bellman-Ford 或 SPFA。

Floyd 管多源(所有点对之间),代码短到不像算法,三重循环:

for (int k = 0; k < V; k++)
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];

含义:「允许经过前 k 个中转点的 i 到 j 最短路」逐层放宽,是动态规划(第 10 章)在图上的样板。O(V³) 的代价决定它只配小图(几百个顶点),但支持负权边、一次算清全部点对,小型城市地图、航空中转分析仍常用。

两张算法分工表收束本章:MST 问题,稀疏图 Kruskal、稠密图 Prim;最短路,单源非负 Dijkstra、全对稠密 Floyd、有负权 Bellman-Ford。它们的公共精神是贪心 + 正确性证明(MST 的切分定理、Dijkstra 的非负前提),「贪心敢不敢用」永远是「能否证明贪了不吃亏」,这句话到第 10 章贪心章会再深挖。

常见错误

  • BFS 忘了入队时标记访问。出队时才标记,同一节点会被重复入队,队列爆炸(这是 BFS 写成 O(V·E) 的头号原因)。
  • 邻接表建无向图只加一条边。u→v 加了,v→u 忘加,遍历直接漏掉半个图。add_edge 要调用两次。
  • Dijkstra 碰负权。结果不报错、只是错,比崩溃更难查;写前先问一句「边权可能为负吗」。

练习

  1. 实现:BFS 求无权图单源最短路(队列 + prev 数组回溯路径),拿一个 6 点图验证路径确实是「最少边数」的。
  2. 手算:对教材经典图(V 为 0 到 5)分别跑 Kruskal 和 Prim(从 0 起),写出每一步选边与被拒边(成环)的清单,验证结果边权和相等。
  3. 动手:构造一个带负权边的小图,分别跑 Dijkstra(手算)和 Floyd,展示 Dijkstra 给出错误答案的具体时刻,把它记成你的「肌肉记忆警告」。
  4. 思考:社交网络「六度分隔」实验,BFS 找两人间隔为什么比 DFS 合理?如果图存成邻接矩阵,十亿用户(10⁹ 顶点)的矩阵多大?这个数字解释了为什么社交图谱一定用邻接表(或边表)存储。
豫ICP备2026027944号