第22章 基本图算法

导读

图（Graph）是计算机科学中最重要的数据结构之一，用于表示对象之间的关系。从社交网络到交通系统，从互联网到电路板设计，图的应用无处不在。本章将介绍图的基本概念、表示方法和基础算法，包括广度优先搜索、深度优先搜索、拓扑排序和强连通分量。

掌握图算法是理解更高级算法（如最短路径、网络流）的前提。图算法在理论和实践中都有广泛的应用，是算法学习的核心内容。

核心概念详解

22.1 图的基本概念

图的定义：

图G = (V, E)，其中V是顶点集，E是边集。

图的类型：

• 无向图：边没有方向，{u,v} = {v,u}
• 有向图：边有方向，(u,v) ≠ (v,u)
• 加权图：边有权重
• 无权图：边没有权重
• 简单图：无自环、无重边
• 多重图：允许重边

术语：

• 相邻（Adjacent）：两个顶点之间有边相连
• 关联（Incident）：边与顶点的关系
• 度（Degree）：与顶点关联的边数
• 入度/出度：有向图中进入/离开顶点的边数
• 路径（Path）：顶点序列，相邻顶点之间有边
• 环（Cycle）：起点和终点相同的路径
• 连通（Connected）：任意两点间有路径
• 强连通：有向图中任意两点互相可达

22.2 图的表示

邻接矩阵：

n×n矩阵A，A[i][j] = 1表示边(i,j)存在。

• 优点：O(1)查询边
• 缺点：空间O(V²)，不适合稀疏图

邻接表：

每个顶点维护一个邻居列表。

• 优点：空间O(V+E)，适合稀疏图
• 缺点：查询边需要O(degree)

选择：

• 稠密图（E ≈ V²）：邻接矩阵
• 稀疏图（E << V²）：邻接表

22.3 广度优先搜索（BFS）

基本思想：

从源点开始，逐层扩展，先访问距离为1的顶点，再访问距离为2的顶点，以此类推。

算法：

BFS(G, s)
    for each vertex u in G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = ∅
    ENQUEUE(Q, s)
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each v in G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.π = u
                ENQUEUE(Q, v)
        u.color = BLACK

时间复杂度：O(V + E)

空间复杂度：O(V)

应用：

• 最短路径（无权图）
• 连通性检测
• 层序遍历

22.4 深度优先搜索（DFS）

基本思想：

从源点开始，尽可能深地探索，直到无法继续，然后回溯。

算法：

DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(u)

DFS-VISIT(u)
    time = time + 1
    u.d = time        // 发现时间
    u.color = GRAY
    for each v in G.Adj[u]
        if v.color == WHITE
            v.π = u
            DFS-VISIT(v)
    u.color = BLACK
    time = time + 1
    u.f = time        // 完成时间

时间复杂度：O(V + E)

空间复杂度：O(V)

DFS的性质：

• 生成DFS森林
• 括号结构：顶点u的活动区间[d[u], f[u]]
• 父子关系：v是u的子节点当且仅当v在u的活动区间内被发现

22.5 拓扑排序

问题描述：

对有向无环图（DAG）的顶点进行线性排序，使得对于每条边(u,v)，u在v之前。

应用：

• 任务调度
• 课程先修关系
• 编译依赖

算法1：基于DFS：

TOPOLOGICAL-SORT(G)
    调用DFS(G)
    当每个顶点完成时，将其插入链表头部
    返回链表

算法2：Kahn算法（基于入度）：

TOPOLOGICAL-SORT-KAHN(G)
    计算所有顶点的入度
    将入度为0的顶点加入队列Q
    while Q ≠ ∅
        u = DEQUEUE(Q)
        输出u
        for each v in G.Adj[u]
            入度[v]--
            if 入度[v] == 0
                ENQUEUE(Q, v)

时间复杂度：O(V + E)

22.6 强连通分量

定义：

有向图的强连通分量（SCC）是最大的顶点集合，其中任意两点互相可达。

Kosaraju算法：

STRONGLY-CONNECTED-COMPONENTS(G)
    调用DFS(G)，计算每个顶点的完成时间
    计算G的转置图G^T
    按完成时间降序，对G^T调用DFS
    每棵DFS树是一个强连通分量

Tarjan算法：

一次DFS即可找出所有SCC，使用栈和low链接值。

时间复杂度：O(V + E)

22.7 连通分量

无向图的连通分量：

使用BFS或DFS找出所有连通分量。

CONNECTED-COMPONENTS(G)
    for each vertex u in G.V
        u.component = 0
    cc = 0
    for each vertex u in G.V
        if u not visited
            cc++
            BFS(G, u)    // 标记同一连通分量

22.8 双连通分量

关节点（Articulation Point）：

删除后使图不连通的顶点。

桥（Bridge）：

删除后使图不连通的边。

双连通分量：

没有关节点的最大子图。

22.9 图算法的应用

社交网络分析：

• 连通分量：社交圈子
• 最短路径：六度分隔
• 中心性：影响力分析

网页排名：

• PageRank：基于随机游走的排名
• HITS：Hub和Authority分析

电路设计：

• 连通性检测
• 布线优化
• 故障分析

编译器优化：

• 控制流图分析
• 死代码消除
• 循环优化

22.10 图的遍历策略

BFS vs DFS：

重要知识点

知识点1：BFS的最短路径性质

BFS保证找到无权图中从源点到所有可达顶点的最短路径。这是因为BFS按距离递增的顺序访问顶点。

知识点2：DFS的时间戳

DFS为每个顶点记录发现时间d和完成时间f。时间戳揭示了图的深度结构，是许多图算法的基础。

知识点3：拓扑排序的存在性

有向图存在拓扑排序当且仅当它是有向无环图（DAG）。如果图中有环，则不存在拓扑排序。

知识点4：强连通分量的性质

强连通分量将图分解为最大强连通子图。缩点后得到的DAG称为分量图。

知识点5：图表示的选择

邻接矩阵和邻接表各有优劣。选择取决于图的密度和需要的操作。

常见误区

误区1：BFS和DFS只能用于连通图

BFS和DFS可以处理非连通图。对于非连通图，需要对每个未访问的顶点调用BFS/DFS。

误区2：拓扑排序只有一种

一个DAG可能有多个拓扑排序。拓扑排序不唯一。

误区3：强连通分量就是连通分量

强连通分量针对有向图，要求双向可达。连通分量针对无向图，只要求单向可达。

误区4：DFS一定比BFS慢

DFS和BFS的时间复杂度相同，都是O(V+E)。选择取决于具体应用。

误区5：图算法不需要考虑图的表示

图的表示直接影响算法的效率。选择不当可能导致性能问题。

实践应用

应用1：社交网络

图算法用于：

• 好友推荐
• 社区检测
• 信息传播分析

应用2：任务调度

拓扑排序用于：

• 项目计划
• 课程安排
• 构建系统

应用3：网络分析

图算法用于：

• 路由优化
• 流量分析
• 故障检测

应用4：生物信息学

图算法用于：

• 基因调控网络
• 蛋白质相互作用
• 代谢通路分析

应用5：编译器

图算法用于：

• 控制流分析
• 数据流分析
• 寄存器分配

22.11 BFS和DFS的详细分析

BFS的正确性证明：

定理：BFS能正确计算从源点s到所有可达顶点的最短距离。

证明（归纳法）：

• 基础：d[s] = 0，正确
• 归纳：假设所有在队列中的顶点距离正确。当出队顶点u时，对于u的每个白色邻居v，d[v] = d[u] + 1。由于BFS按层遍历，v不可能通过更短的路径到达（否则v已经被发现）。因此d[v]是最短距离。

BFS树的性质：

BFS生成一棵以s为根的树。树中从s到v的路径对应原图中从s到v的最短路径。但BFS树的最短路径不唯一——不同的BFS执行可能产生不同的BFS树。

DFS的括号化定理：

定理：顶点u和v的活动区间[d[u], f[u]]和[d[v], f[v]]要么完全不相交，要么一个完全包含另一个。

推论：

• 如果v是u的后代，则v的区间完全包含在u的区间内
• 如果v在u的区间内被发现，则v是u的后代
• 如果v在u完成之后才被发现，则v不在u的子树中

DFS边的分类：

DFS遍历过程中，边可以分为四类：

• 树边（Tree Edge）：DFS树中的边
• 后向边（Back Edge）：指向祖先的边，表明有环
• 前向边（Forward Edge）：指向后代的非树边
• 交叉边（Cross Edge）：连接不同子树的边

22.12 拓扑排序的深入分析

拓扑排序的唯一性：

一个DAG可能有多个拓扑排序。拓扑排序唯一当且仅当图是一条链（存在哈密顿路径）。

所有拓扑排序的枚举：

使用回溯法可以枚举所有拓扑排序：

找所有入度为0的顶点

依次选择每个入度为0的顶点

移除该顶点及其出边，更新入度

递归处理

回溯恢复

拓扑排序的应用实例：

课程安排：

• 每门课程是一个顶点
• 先修关系是有向边
• 拓扑排序给出合法的修课顺序

编译依赖：

• 每个源文件是一个顶点
• 包含关系是有向边
• 拓扑排序给出编译顺序

电子表格计算：

• 每个单元格是一个顶点
• 公式引用是有向边
• 拓扑排序给出计算顺序

22.13 强连通分量的深入分析

Kosaraju算法的正确性证明：

关键引理：如果C和C'是两个不同的强连通分量，且C到C'有边，则C的最大完成时间大于C'的最大完成时间。

证明思路：

• 在第一次DFS中，如果先访问C中的顶点，由于C到C'有边但C'到C没有边，C的DFS会先完成
• 在转置图中，边方向反转，C'到C有边
• 按完成时间降序处理，先处理C（完成时间更大）
• 在转置图中从C出发只能到达C中的顶点

Tarjan算法：

Tarjan算法在一次DFS中找出所有强连通分量：

• 维护一个栈和一个low值数组
• low[u] = min(d[u], min{d[w] : w是u通过后向边可达的祖先})
• 当low[u] == d[u]时，u是一个SCC的根

分量图：

将每个SCC缩为一个顶点，得到的图称为分量图。分量图一定是DAG。这个性质在很多算法中很有用——先求SCC，再在DAG上处理。

22.14 双连通分量和关节点

关节点检测算法：

使用DFS检测关节点：

• 维护dfn（发现时间）和low值
• low[u] = min{dfn[v] : v通过子树中的后向边或前向边可达}
• 如果u不是根且存在子节点v使得low[v] ≥ dfn[u]，则u是关节点

桥的检测：

桥是不属于任何环的边。删除桥会使图不连通。

• 使用DFS，如果边(u,v)满足low[v] > dfn[u]，则(u,v)是桥

双连通分量：

没有关节点的最大连通子图。等价地，任意两点之间存在两条点不相交路径。

22.15 图的特殊类型和算法

欧拉回路：

经过每条边恰好一次的回路。存在条件：图连通且每个顶点度数为偶数。使用Hierholzer算法在O(E)时间内找到。

哈密顿回路：

经过每个顶点恰好一次的回路。判定问题是NP完全的。

二分图：

顶点可以分为两个不相交的集合，每条边连接两个集合中的顶点。二分图检测使用BFS/DFS着色。

平面图：

可以在平面上画出且边不相交的图。库拉托夫斯基定理：图是平面图当且仅当不包含K₅或K₃,₃的细分。

本章小结

本章深入介绍了基本图算法。我们学习了：

图的基本概念：顶点、边、度、路径、连通性、有向图与无向图等。

图的表示：邻接矩阵（稠密图）和邻接表（稀疏图），各有优劣。

BFS：逐层搜索，保证无权图最短路径。BFS树的性质和正确性证明。

DFS：深入搜索，产生时间戳和边的分类。括号化定理揭示了图的深度结构。

拓扑排序：DAG的线性排序。基于DFS和Kahn算法两种实现。

强连通分量：Kosaraju算法和Tarjan算法。分量图是DAG。

双连通分量：关节点和桥的检测，双连通分量的计算。

特殊图类型：欧拉回路、哈密顿回路、二分图、平面图等。

图算法是算法学习的核心内容。深入掌握基本图算法的原理和实现，是理解最短路径、网络流等高级算法的前提。

关键术语

思考题

证明：无向图中，如果存在从u到v的路径，则BFS从u出发一定能到达v。

设计一个算法，判断有向图是否有环。

分析Kosaraju算法的正确性，为什么需要对转置图按完成时间降序DFS。

设计一个算法，找出无向图的所有关节点。