一、起源:多对多关系的表达需求

1.1 树把关系约束在层次与单亲

线性结构承诺「一个元素至多一个前驱、一个后继」,树把这一承诺放宽到「一个元素至多一个父节点,可以有多个子节点」,见 二叉树与二叉搜索树。放宽带来了层次关系的表达能力,同时也留下了三条硬性约束:

  • 父节点唯一。任何一个节点至多隶属一个上级。组织架构中的兼岗、物料的多级归类、一个人的多重角色,都无法在树上表达。
  • 无环。从任一节点出发沿父节点上行必然终止于根,因此树中不存在回路。「任务 A 依赖 B、B 依赖 C、C 又依赖 A」这类循环依赖在树的结构中无法出现,而它恰恰是实际系统中的常见缺陷形态。
  • 路径唯一。任意两点之间恰有一条路径(沿树边的唯一简单路径)。这一性质使可达性判断退化为祖先关系判断,代价很低;但也意味着无法表达「两条不同的通路」「多个前置条件」这类关系。

树的这些性质不是缺陷,而是取舍:正是因为承认了父节点唯一与无环,树上的操作才能做到 O(log n) 或 O(n),并且形态由节点数唯一决定了一个数量级的上界。一旦放弃这些约束,就必须付出新的表示与遍历代价,这正是图要解决的问题。

1.2 多对多关系的三类普遍形态

依赖关系。 编译系统中的源文件与头文件、构建系统中的任务与产物、包管理中的模块与版本、配置项之间的引用、数据库对象的约束,本质都是「若干前置条件满足后才能执行」。依赖关系天然是多对多的:一个任务可能有多个前置,一个前置可能被多个任务共享;更重要的是,依赖关系可能出现环,而环意味着无法排序、无法执行。

网络结构。 主机、交换机、路由器、服务实例、存储节点之间的连接构成一张网络。连通性(两端是否可达)、可达性(从 A 能否到 B)、割点与桥(哪些节点或链路的失效会切断网络)、故障影响面(某个节点失效会波及哪些服务)都是这张图上的问题。单点故障的识别与量化见 linux: 高可用与集群 中单点故障与可用性度量一节。

状态转移。 把问题的每个状态视为一个点,把一次合法的状态变更视为一条有向边,则「从初始状态到目标状态是否存在一系列操作」变成图上的可达性问题,「最少需要几步」变成最短路径问题。棋类博弈、编译器中的寄存器分配、物流路径规划、配置项的组合校验都属于这一类。这类图往往不在内存中显式建立,而是由状态生成规则(隐式图)按需展开。

三类形态的共同点是多对多:一个元素的关联对象不唯一,且关联关系本身携带方向、权重或属性。线性表与树无法承载这种关系,因为它们的结构已经通过「唯一前驱」「唯一父节点」把关系压到了每条元素上。

1.3 遍历是绝大多数图算法的骨架

图的基本操作可以分为两类:一类是局部操作(增加或删除一个点、一条边,查询某个点的邻居、判断一条边是否存在),代价由所选的表示方法决定;另一类是全局操作,需要按某种次序访问全部或部分顶点与边,这类操作统一称为遍历。

几乎所有权重之外的图算法都建立在一到两次遍历之上:

算法 所需的遍历 遍历中维护的信息
可达性与连通性判断 一次 DFS 或 BFS 访问标记
连通分量计数 一次遍历覆盖全部未访问点 访问标记、分量编号
环检测 一次 DFS 访问状态(未访问、在栈中、已完成)或父节点
二分图判定 一次遍历 颜色数组
拓扑排序 一次遍历 入度计数,或完成时间戳
割点与桥、双连通分量 一次 DFS 发现时间与低值(low)
无权图最短路径 一次 BFS 距离数组
生成树 一次遍历 前驱(父)数组
强连通分量 一到两次遍历 完成序或低值与栈

因此遍历的复杂度就是这些算法的复杂度上界:遍历本身是 O(n + m),在其上附加的维护工作若为常数级,算法整体仍是 O(n + m);若每次访问邻居时还做了线性或对数级的额外操作,复杂度随之上升。把遍历写成什么样,决定了后续所有算法的代价与正确性,这也是遍历值得单独讨论的原因。

1.4 与 ADT 及存储结构两条主线的承接

从抽象数据类型的视角看,图是一种 ADT:数据对象是顶点集合与边集合,数据关系是边对顶点的关联,基本操作包括增加与删除顶点、增加与删除边、查询某顶点的邻接点、判断两顶点是否相邻、以及遍历。邻接矩阵、邻接表、边集数组是同一 ADT 的不同存储实现,接口一致而代价不同,这一分离关系见 抽象数据类型(ADT)。

从存储结构看,图是数组与链表两种组织方式的重新组合:邻接矩阵延续数组的连续存储(下标寻址、判边常数时间、空间由顶点数决定),邻接表延续链式存储(按需分配、空间由边数决定、访问邻居需要跳转)。因此「连续存储的定位优势」与「分散存储的修改优势」这一根本矛盾在图上再次出现,只不过衡量单位从「元素个数」变成了「顶点数与边数」。两种布局在缓存局部性上的差异、节点开销的估算方式见 数组与链表。遍历所用容器的选择依据(深度优先用栈、广度优先用队列)见 栈与队列。


二、原理

2.1 基本概念

2.1.1 术语与分类

术语 含义
顶点与边 图的组成单元;边连接两个顶点,可带方向与权重
有向图 边有方向,记为 (u, v),u 为起点、v 为终点
无向图 边无方向,记为 {u, v},两个端点地位对等
带权图 边上附加数值(距离、代价、容量、时延);无权图可视为所有权为 1
度 deg(v) 无向图中与该顶点关联的边数
入度与出度 有向图中指向 v 的边数(入度)与从 v 出发的边数(出度)
路径 顶点序列,相邻两项之间有一条边
路径长度 无权图中为边数;带权图中为边权之和
回路(环) 起点与终点相同的路径
简单路径 顶点不重复出现的路径
简单回路 除起点终点外顶点不重复的回路
连通 无向图中两顶点之间存在路径
连通分量 无向图的极大连通子图
强连通 有向图中两顶点互相可达
强连通分量 有向图的极大强连通子图
弱连通 有向图忽略方向后连通
稠密图与稀疏图 边数与 n² 的比值接近则为稠密,m = O(n) 量级则为稀疏
自环 两个端点相同的边
重边(平行边) 同一对顶点之间存在多条边
完全图 任意两个不同顶点之间都有边
二分图 顶点可划分为两个集合,所有边都跨集合
生成树 含全部顶点、恰有 n − 1 条边的连通无环子图

2.1.2 度与边数的关系

无向图中每条边为两个端点各贡献 1 度,因此

无向图:Σ deg(v) = 2m

推论:度为奇数的顶点个数必为偶数(因为总和为偶数,奇数度顶点必须成对出现)
      完全图 K_n 的边数 m = n(n − 1) / 2

有向图中每条边贡献一个出度与一个入度,因此

有向图:Σ 出度(v) = Σ 入度(v) = m
        有向完全图的边数 m = n(n − 1)

这两条关系在实现中直接可用:入度的总和等于边数,是校验边表是否完整的一项断言;「奇数度顶点为偶数个」是欧拉路径存在性判定的前置条件。

2.1.3 稠密与稀疏的数量级

边数的取值范围是 0 到 n(n−1)/2(无向)或 n(n−1)(有向)。这一范围内的两个极端对应两种截然不同的存储选择:

n = 10⁴ 时
    完全无向图      m ≈ 5 × 10⁷
    稀疏图(m ≈ 2n) m ≈ 2 × 10⁴

两者相差三个数量级,因此「用 n² 还是用 m 表达空间代价」直接决定了内存是否够用

判断稀疏与稠密只用一条经验规则:m 与 n² 的比值远小于 1,且 m = O(n) 时按稀疏处理;m 接近 n²/2 时按稠密处理。工程中的图绝大多数是稀疏的:网络拓扑的平均度通常在 2 至 10 之间,任务依赖图的平均出度通常在个位数,社交关注关系的平均出度在几十到几千之间,都远小于 n。

2.2 表示方法

2.2.1 邻接矩阵

用一个 n × n 的二维结构 A,A[i][j] 表示从 i 到 j 是否存在边(无权图)或边的权重(带权图)。

无权无向图:A[i][j] = A[j][i] = 1(存在边)
            存储上只需存上三角即可省一半空间,但访问时需要定序,实现复杂度上升
无权有向图:A[i][j] = 1(存在边 i → j),A[j][i] 与它无关
带权图:    A[i][j] = w(存在边),不存在边用哨兵值(0、−1 或无穷大)表示
自环:      A[i][i] = 1
重边:      矩阵无法区分同一对顶点之间的多条边,只能保留最值或求和
操作 代价 说明
判断 (i, j) 是否有边 O(1) 一次下标寻址
查询某条边的权重 O(1) 同上
修改一条边 O(1) 无向图需同时改两个位置
枚举 v 的全部邻居 O(n) 必须扫描整行,与 v 的实际度无关
遍历全部顶点与边 O(n²) 无论 m 是多少
空间 O(n²) 与 m 无关

两个关键后果:

  1. 枚举邻居的代价与顶点的度无关。稀疏图中一个顶点的度可能只有 3,却要扫描整行 n 个位置。这是邻接矩阵在稀疏图上最致命的缺点:遍历的总代价从 O(n + m) 退化为 O(n²)。
  2. 空间与边数无关。n = 10⁵ 时,用 boolean[][] 需要 10¹⁰ 字节,用位图压缩到 n²/8 位也需约 1.25 GB,而这份空间中有 99.999% 是空的。位图的组织方式与内存占用见 位图与布隆过滤器。

邻接矩阵的优势场景因此很明确:n 较小(数百至数千)、边稠密、且大量操作是「判断两点之间是否有边」或「查询边权」。矩阵乘法形式的图算法(传递闭包、Floyd-Warshall 最短路)也依赖这种表示,因为它们的核心操作是按行与列的整体运算,正好匹配连续存储的访问模式。

2.2.2 邻接表

为每个顶点维护一个容器,保存它的全部邻居。整体空间为 O(n + m)。

无权有向图:adj[u] = { v | 边 u → v 存在 }
无权无向图:每条边在 adj[u] 与 adj[v] 各记录一次,因此总记录数为 2m
带权图:    adj[u] 中保存 (v, w) 二元组,或用两个平行数组分别存目标与权重
自环与重边:自然支持,重边表现为同一目标出现多次
操作 代价 说明
枚举 v 的全部邻居 O(deg(v)) 与该顶点的度成正比
遍历全部顶点与边 O(n + m) 与规模成正比,稀疏图上最优
判断 (i, j) 是否有边 O(deg(i)) 需要扫描 i 的邻居;若邻接表本身有序或另建哈希索引可降到 O(log deg) 或期望 O(1)
查询边权 O(deg(i)) 同上
修改一条边 O(deg(i)) 需要在邻居表中定位(尾部追加为摊还 O(1))
空间 O(n + m) 与边数成正比

邻接表的关键性质是把「枚举邻居」这一操作做成与度相关,而绝大多数图算法的核心循环正是枚举邻居,因此邻接表在稀疏图上把遍历代价从 O(n²) 拉回 O(n + m)。代价落在判边上:判边需要扫描邻居,而在需要频繁判边的场景(如冲突检测、环路判定的即时查询)中,可以额外维护一个哈希集合做索引,用 O(n + m) 的额外空间换取期望 O(1) 的判边,哈希结构的冲突处理与扩容代价见 散列表。

邻接表还有一个细节会被忽略:邻居的存储顺序决定了遍历的结果顺序。若需要输出稳定(例如可复现的拓扑序、字典序最小的路径),必须在遍历前对每个顶点的邻居排序,或在插入时保持有序。若需要判重(避免同一对顶点重复记录),通常也是在插入时检查或将邻居排序后去重。这两项都属于「用一次排序换取后续确定性」的做法。

2.2.3 边集数组

把全部边存成一个数组,每个元素记录 (u, v) 或 (u, v, w)。

操作 代价 说明
遍历全部边 O(m) 与邻接表的全图遍历同阶,但只访问边本身
按权重排序 O(m log m) 支持「按边权从小到大处理」的算法
枚举某顶点的邻居 O(m) 需要扫描整个边表,代价与边数无关地放大
判断两顶点是否相邻 O(m) 同上
空间 O(m) 三种表示中最小

边集数组的适用面由「按边处理的算法」决定。这类算法不关心「某个顶点有哪些邻居」,只关心「全部边构成什么集合」,因此边表正好匹配:

  • Kruskal 最小生成树:把边按权重排序,依次判断两端是否已在同一连通分量中(用并查集),加入不构成环的边。整个算法是「排序 + 遍历边 + 查并查集」,不需要邻接关系。
  • Bellman-Ford 最短路:每轮遍历全部边做一次松弛,共 n − 1 轮。松弛操作只需要边的两个端点与权重。
  • 欧拉路径判定:先按度数筛选候选起点,再按边逐个走过(配合 Hierholzer 算法时仍需要邻接结构)。
  • 边表的校验与统计:统计边数、顶点度分布、最大权重、重边数量,这类任务只需一次线性扫描。

反之,凡是需要「沿着边一跳一跳地走」的算法(DFS、BFS、Dijkstra)都不适合直接用边集数组,因为每次跳转都要重新扫描整张边表,代价放大为 O(n·m)。

2.2.4 链式前向星与压缩稀疏行

邻接表在概念上简单,但用「链表节点」或「容器数组」实现时会有额外开销:每个链表节点多一次间接寻址,每个容器对象多一份对象头,且节点分散在堆中导致遍历时缓存命中率低。两种工程化的紧凑表示消除了这些开销,都只用少数几个平行数组。

链式前向星(forward star) 用三个数组模拟邻接表:

head[n]      每个顶点的第一条边的编号,初始为 −1
to[m]        每条边的终点
nxt[m]       同一起点的下一条边的编号,构成链表
w[m]         每条边的权重(带权图)

加边 add(u, v, w):
    to[cnt] = v; w[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; cnt++

遍历顶点 u 的全部邻居:
    for (int e = head[u]; e != −1; e = nxt[e]) {
        int v = to[e];
    }

它保留「头插法」的链表语义(后加入的边先被访问),全部数据放在连续数组中,因此遍历时几乎总是命中同一批缓存行。无向图加边时调用两次。

压缩稀疏行(Compressed Sparse Row,CSR) 用两个数组表达,并把每个顶点的邻居排成连续的一段:

offset[n + 1]   顶点 i 的邻居在 target 中的区间为 [offset[i], offset[i + 1])
target[2m]      全部邻居目标按顶点顺序排列
weight[2m]      对应权重(可选)

构造需要两步:
    1. 统计每个顶点的出度,前缀和得到 offset
    2. 再次扫描边表,把目标依次填入对应区间(用游标数组记录每个顶点已填写的位置)

CSR 的优势有三点:空间最小(除两个计数数组外没有额外指针);邻居连续存放,遍历的缓存局部性接近数组扫描;两顶点邻居区间可以 O(1) 定位,便于做区间交集等操作。代价是构造后不易增量修改(增删边会导致区间移位),因此适用于「一次性建图、多次查询」的场景,例如搜索引擎的网页链接图、推荐系统的用户行为图、图计算框架的输入格式。

2.2.5 几种表示的对比与选型

维度 邻接矩阵 邻接表 边集数组 链式前向星 / CSR
空间 O(n²) O(n + m) O(m) O(n + m),常数最小
判边 (u, v) O(1) O(deg(u)) O(m) O(deg(u))
枚举 v 的邻居 O(n) O(deg(v)) O(m) O(deg(v)),连续性最好
全图遍历 O(n²) O(n + m) 不适用 O(n + m)
按权重排序边 需先提取,O(n² + m log m) O(m log m) O(m log m),直接可排 O(m log m)
增量增删边 O(1) 摊还 O(1) 追加;删除 O(deg) O(1) 追加 增边 O(1);删边困难
适用形态 稠密图、判边频繁、矩阵运算类算法 通用,稀疏图默认选择 按边处理的算法 大规模静态图、性能敏感场景

选型的三条判断:

  1. 先看 n 与 m 的量级。n 超过万余且 m = O(n) 时,邻接矩阵在空间上已不可行,只能选邻接表或 CSR;n 在数百以内时,矩阵的常数优势与判边优势往往更划算。
  2. 再看主要操作。以「枚举邻居」为主的遍历算法选邻接表;以「判边、查边权」为主的算法选矩阵或带哈希索引的邻接表;只按边处理的算法选边集数组。
  3. 最后看是否需要动态修改。需要频繁增删边或顶点时,CSR 与静态数组结构不合适,应回到邻接表(容器或链式前向星)。

2.3 深度优先遍历

2.3.1 策略与递归实现

深度优先遍历(Depth First Search,DFS)的策略是沿一条路径尽可能深入,直到无法继续再回退到最近的分叉点。回退的目标永远是最近一次做出的选择,因此所需的容器是后进先出的栈,这一对应关系见 栈与队列。

DFS(u):
    标记 u 为已访问
    访问 u(前序位置)
    for each 邻居 v of u:
        if v 未被访问:
            记录 pred[v] = u
            DFS(v)
    结束对 u 的处理(后序位置)
void dfs(List<List<Integer>> adj, int u, boolean[] visited, int[] pred) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            pred[v] = u;                 // 记录前驱,构成 DFS 树的一条边
            dfs(adj, v, visited, pred);
        }
    }
}

三项记录各自承担不同职责,缺一不可:

  • 访问标记。防止在同一条路径上绕回已访问的顶点,是无环终止的保证;缺失会造成无限递归或无限循环。
  • 前驱数组。记录每个顶点是从哪个顶点进入的,全部非空前驱构成一棵DFS 树(对非连通图则是 DFS 森林)。
  • 访问位置。在「进入顶点时」还是在「处理完邻居后」执行附加逻辑,决定了遍历具备前序还是后序语义,这一点对后续应用(拓扑排序、强连通分量)是决定性的。

2.3.2 显式栈实现

把递归改写为显式栈的动机与树遍历一致:递归深度受线程栈容量限制,改写到堆上后容量上限由堆大小决定,且可以在迭代过程中插入中断、暂停与恢复逻辑。改写时有一处关键差异需要处理——递归的「进入」与「返回」是两个时刻,而朴素栈实现只保留了「进入」。

void dfsIterative(List<List<Integer>> adj, int s, boolean[] visited) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(s);
    visited[s] = true;                       // 入栈时标记:避免同一顶点被多次压入
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;           // 关键:在压栈时标记,而不是在弹栈时
                stack.push(v);
            }
        }
    }
}

若把标记动作放在弹栈时,同一顶点会被多个已访问邻居重复压入,栈的容量可能增长到 O(m) 而不是 O(n),访问次数也随之膨胀。在压栈时标记是这段代码的正确性核心。

这一写法与递归 dfs 的访问次序并不完全等同:递归先深度探索第一个邻居的整棵子树,再处理第二个邻居;而压栈式写法会把全部未访问邻居按顺序压入,出栈顺序与压栈顺序相反,因此展开次序与递归相反。若要求与递归完全一致的次序,需要把邻居逆序压栈;若需要后序语义(例如在子树处理完后再记录顶点),则需要向栈中压入「顶点 + 状态」的二元组,第一次弹出时压回自身与邻居、第二次弹出时执行后序处理。这类改写与树的后序迭代实现同源,见 二叉树与二叉搜索树 中后序标记法一节。

2.3.3 时间复杂度与递归深度

表示 单次 DFS 的时间 依据
邻接表 / CSR / 前向星 O(n + m) 每个顶点进入一次,每条边被检查两次(无向)或一次(有向)
邻接矩阵 O(n²) 每个顶点都要扫描整行,与度无关
边集数组 O(n·m) 每次需要枚举邻居都要扫描整个边表

递归深度是 DFS 与 BFS 最重要的实现差异。DFS 的递归深度等于当前路径的长度,在链状图或退化结构上可以达到 n。以 Java 默认线程栈(约数百 KB 至 1 MB)估算,递归深度在数千至上万量级即可能耗尽栈空间并抛出 StackOverflowError;Python 的默认递归上限约 1000 层,更早触发。三处结论:

  1. 深度与图的形状绑定,而不是与规模的一阶量绑定。稀疏图的一般形态下深度为 O(log n) 量级,但路径图、长链依赖图、以及内存指针构成的隐式引用图都容易出现线性深度。
  2. 显式栈只是把空间从线程栈搬到堆,量级不变(仍是 O(n) 最坏),但可容纳的深度高出数个数量级,且溢出表现为堆内存不足而非直接崩溃。
  3. 对深度不可控的输入,应在建模阶段就把 DFS 改成迭代形式,而不是等到栈溢出后再修改;这类改写涉及状态语义,越晚处理成本越高。

2.3.4 DFS 树与时间戳

DFS 在遍历过程中形成的结构信息是其后续用途的来源。

DFS 树:全部「由未访问顶点进入」的边构成;其余边按起止顶点的访问状态分类

有向图的四类边:
    树边(tree edge)      进入未访问顶点
    回边(back edge)      指向「仍在递归栈中」(处于灰色)的祖先 → 存在回边等价于存在环
    前向边(forward edge) 指向已完成(黑色)的后代
    横叉边(cross edge)   指向已完成且非后代的顶点

无向图只有两类边:树边与回边(前向边与横叉边会因访问次序退化为回边)

发现时间 disc[u] 与完成时间 fin[u] 是 DFS 的副产品:进入顶点时记录 disc,处理完全部邻居时记录 fin。这两个时间戳带来三项可直接使用的性质:

  1. 区间包含关系刻画祖先关系。u 是 v 的祖先,当且仅当 disc[u] < disc[v] 且 fin[v] < fin[u],即 u 的时间区间包含 v 的区间。这一性质是 Tarjan 类算法(强连通分量、割点、双连通分量)的基础。
  2. 按时序排列可判定边的类型。由 u 指向 v 的边,若 disc[v] 未产生则为树边;若 disc[v] > disc[u] 且未完成,则为回边;若已完成且 disc[v] > disc[u],为前向边;若已完成且 disc[v] < disc[u],为横叉边。判环只需检查是否存在回边。
  3. 完成时间的逆序是一个拓扑序(限于有向无环图)。原因是:对于任意一条有向边 u → v,若它是树边或前向边,则 v 先完成,fin[v] < fin[u];若是横叉边,v 也在更早的子树中完成。因此按完成时间从大到小排列顶点,所有边都从排在前的顶点指向排在后的顶点。

2.4 广度优先遍历

2.4.1 队列实现与层次划分

广度优先遍历(Breadth First Search,BFS)的策略是先访问所有距离起点为 1 的顶点,再访问距离为 2 的顶点。展开顺序必须等于发现顺序,因此所需容器是先进先出的队列。

BFS(s):
    距离 dist[s] = 0,s 入队
    while 队列非空:
        u = 队头出队
        for each 邻居 v of u:
            if v 未被访问:
                标记 v 已访问,dist[v] = dist[u] + 1,pred[v] = u
                v 入队
void bfs(List<List<Integer>> adj, int s, int[] dist, int[] pred) {
    Arrays.fill(dist, -1);                  // −1 表示未访问
    Queue<Integer> queue = new ArrayDeque<>();
    dist[s] = 0;
    queue.offer(s);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                pred[v] = u;
                queue.offer(v);             // 入队时即标记,见 3.2 节
            }
        }
    }
}

层次信息天然隐含在队列中:同一层的顶点在队列里是连续的一段。需要按层处理时,在每轮循环开始前记录当前队列长度作为本层的顶点数,处理恰好这么多个顶点后再进入下一层;这一「先固定层大小」的做法与树的层序遍历完全一致。

2.4.2 无权图最短路径的性质与证明直觉

BFS 在无权图(或所有边权相等的图)上给出的 dist 就是最短路径长度。论证的思路是三条:

设 δ(v) 为从 s 到 v 的最短路径长度(边数)。

命题:BFS 中 dist[v] = δ(v)。

论证:
    1. 非递减性:BFS 的出队顺序中 dist 值单调不减。
       队列中的顶点满足「队头 dist 为 d、队尾 dist 为 d 或 d + 1」,
       因为一个 dist = d 的顶点只会把 dist = d + 1 的顶点加入队尾。

    2. 上界:dist[v] ≥ δ(v)。
       BFS 中沿前驱数组回溯得到的是一条从 s 到 v 的真实路径,
       长度为 dist[v],而 δ(v) 是所有路径长度的最小值,故 dist[v] ≥ δ(v)。

    3. 下界:dist[v] ≤ δ(v)。
       对 δ(v) 归纳。设 s → ... → u → v 是一条最短路径,则 δ(u) = δ(v) − 1。
       由归纳假设 dist[u] ≤ δ(u)。当 u 出队时,若 v 尚未被标记,
       则 v 会被赋予 dist[u] + 1 ≤ δ(u) + 1 = δ(v);
       若 v 已被标记,则它在更早的时刻被赋予了一个不大于当前值的距离(因为距离随出队顺序非递减)。
       两种情况下都有 dist[v] ≤ δ(v)。

    由上界与下界即得 dist[v] = δ(v)。

结论有两条使用边界:第一次到达某顶点的路径即最短路径,因此只需记录前驱即可还原整条最短路径,不需要在任何时刻回退或更新距离;以及这一性质只在边权相等时成立,边权不等时必须改用 Dijkstra(配合优先队列按距离出队,见 堆与优先队列)或其他带权最短路算法;带权最短路的算法族、负权与负环的处理、最小生成树的割性质与环性质见 最短路径与最小生成树。

2.4.3 双向 BFS 的优化思路

BFS 的代价随层数指数增长:分支因子为 b、目标距离为 d 时,访问的顶点数约为 b^d。双向 BFS 从起点与终点同时展开,两侧在中间相遇,此时各自只需展开 d/2 层,访问量降到约 2·b^(d/2),减少的是指数上的因子。

实现要点有五条:

  1. 两侧各维护一个访问集合(距离表),每轮选择当前层顶点较少的一侧展开,以控制总展开量。
  2. 相遇判定:展开一侧时,若新发现的顶点已出现在对侧的访问集合中,则该顶点的距离为两侧距离之和,最短距离为「所有相遇点中两侧距离之和的最小值」。在无权图中,首次相遇即给出最短距离。
  3. 必须处理「边数为奇数」的情形:两侧距离与可能相差 1,直接把两个距离相加即得到正确答案,不需要额外修正。
  4. 路径还原需要两侧各自的前驱记录,从相遇点向两侧回溯后拼接。
  5. 适用前提是能反向展开。有向图要求反向边可用(通常需要同时维护入边表),无向图天然满足。状态空间搜索中若状态转移不可逆,则不能使用双向 BFS。

2.5 遍历的应用

2.5.1 连通分量计数

对无向图,外层遍历全部顶点,遇到未访问顶点则以其为起点做一次 DFS 或 BFS,并把本次到达的全部顶点归入同一分量,分量计数加一。

count = 0
for v in 全部顶点:
    if v 未被访问:
        count++
        DFS(v) 或 BFS(v)        // 本次到达的全部顶点属于同一连通分量

复杂度为 O(n + m),因为每个顶点与每条边各被访问常数次。判断「整张图是否连通」只需检查计数是否为 1;判断「多少个孤岛」、划分「网络分区」都由这一计数给出。有向图的对应概念是强连通分量(Kosaraju 两遍 DFS、Tarjan 单遍 DFS 配合低值与栈),弱连通分量则把有向边视为无向边后按上述方法统计;强连通分量的两种实现、缩点后的有向无环图及其用途,以及最大流与最小割、二分图匹配等主题见 进阶图算法。

2.5.2 环检测:无向图与有向图的差别

无向图:在 DFS 中遇到一个已访问的邻居 v,若 v 不是当前顶点 u 在 DFS 树中的父节点,则存在环。理由是:在无向图中,非树边必然连接当前顶点与它的某个祖先(不存在横叉边),因此这条非树边与树上的路径共同构成回路。

dfs(u, parent):
    visited[u] = true
    for each 邻居 v of u:
        if v 未访问:
            if dfs(v, u) 返回 true:return true
        else if v ≠ parent:
            return true            // 非父节点的已访问邻居 → 存在环
    return false

一处容易出错的地方是重边与自环:两条顶点相同的平行边会让 v ≠ parent 的判断失效(同一父节点通过另一条平行边被再次访问,被误判为环),而自环需要单独检查 u == v。工程做法是给边编号,判断「是否为进入当前顶点的那一条边」而不是「是否为父节点」。另一种更稳的写法是配合并查集:按任意顺序逐条加入边,若某条边的两个端点已在同一集合中,则该边构成环;这一做法不需要区分父边与重边,代价是 O(m·α(n))。并查集的路径压缩与按秩合并的摊还结论见 复杂度与算法分析 中并查集一节。

有向图:无向图的判据不成立,因为「已访问」不等于「在当前的递归栈上」。必须用三色状态区分:

状态:白色(未访问)、灰色(在当前递归栈中)、黑色(已完成)

dfs(u):
    color[u] = 灰
    for each 出边邻居 v of u:
        if color[v] == 灰:return true      // 回边 → 存在环
        if color[v] == 白 且 dfs(v):
            return true
    color[u] = 黑
    return false

区别的实质是:无向图中「已访问」的祖先只能是祖先(横叉边不存在),因此可以用父节点排除法代替灰色标记;有向图中存在指向已完成的、与当前顶点无祖先关系的横叉边,若把它当作环就会出现误判。判断依据必须落在「是否仍在递归栈上」这一状态上。用发现与完成时间戳表述同一判据:存在回边等价于存在环,即存在边 u → v 使 disc[u] < disc[v] < fin[v] < fin[u]。

2.5.3 二分图判定(染色法)

二分图的等价刻画是「可以用两种颜色给全部顶点染色,使每条边的两端颜色不同」,另一个等价刻画是「不含奇数长度的环」。因此判定方法就是一次遍历加上颜色冲突检查:

color[] 初始为 −1(未染色)
for v in 全部顶点:
    if color[v] == −1:
        color[v] = 0
        从 v 出发做 BFS 或 DFS:
            对每条边 u — v:
                if color[v] == −1:color[v] = 1 − color[u]
                else if color[v] == color[u]:不是二分图,结束

三点结论:

  1. 复杂度 O(n + m),与一次遍历同阶。用 BFS 实现时,图上称为二分图,队列中同一层的顶点颜色相同,因此也可以直接检查「同层顶点之间是否有边」。
  2. 判定结果与「起点选择」无关,非连通图必须对每个连通分量都执行一次,遗漏未访问分量会漏掉冲突。
  3. 二分图判定的直接用途是冲突检测:把「互相冲突的两类元素」建模为边的两端(任务与只能串行执行的资源、用户与互斥的角色、同一时段的两个排班需求),判定二分图即判定能否整体划分为两个互不相交的集合。若判定失败,DFS 中检测到的那条回边给出了一个奇环,可作为冲突原因的定位线索。

2.5.4 拓扑排序

拓扑排序把有向无环图的顶点排成一个线性序列,使每条边的起点都排在终点之前。它是任务调度、依赖解析、编译顺序、包安装顺序的基础。两种实现对应 DFS 与 BFS 两条路径。

Kahn 入度法(BFS 路径):

1. 统计每个顶点的入度
2. 全部入度为 0 的顶点入队
3. while 队列非空:
        u = 出队,输出 u
        for each 出边 (u, v):
            indeg[v]--
            if indeg[v] == 0:v 入队
4. 若输出顶点数 < n,则图中存在环(剩余顶点的入度都不为 0)

DFS 完成序法(DFS 路径):对全部顶点执行 DFS,在顶点完成时(后序位置)把它压入结果栈,最终结果栈的弹出顺序即拓扑序。依据是 2.3.4 节的性质:对有向无环图中的任意边 u → v,v 的完成时间都早于 u,因此按完成时间的逆序排列满足全部边的方向约束。

两种写法的对比:

维度 Kahn 入度法 DFS 完成序法
遍历方式 BFS,队列 DFS,栈或递归
环判定 输出顶点数不足 n 即存在环,天然给出「无法排序的剩余集合」 需要额外维护三色状态检出回边;仅靠完成序无法区分有环与无环
结果不唯一 是(同层顶点次序随意) 是(邻居展开次序决定完成序)
附加能力 入度递减过程可直接支持「按层输出」与并行调度分批 完成序便于与其他 DFS 副产品(低值、强连通分量)合用
递归风险 无(迭代实现) 递归实现存在深图栈溢出风险,需改显式栈

工程上有两点补充:

  • 环的定位。拓扑排序只能给出「存在环」这一事实,但依赖冲突排查需要环上具体包含哪些节点。做法是从剩余顶点(入度不为 0 的顶点)出发做一次 DFS,沿路径一直前进直到回到路径上的某个顶点,即得到一条具体回路;这条回路正是冲突报告中最有价值的信息。
  • 依赖图的规模与层次。Kahn 法按层出队的过程天然给出「第几批可以并行执行」,这与构建系统的并行调度、工作流的并行分支直接对应。依赖编排与工作流引擎的实现见 Java 工作流与规则引擎。

2.5.5 割点与桥与双连通分量

这类问题的共性是「哪些点的移除会破坏连通性」,其解法依赖 DFS 中发现时间与低值两个量。

disc[u]:u 的发现时间
low[u] :从 u 出发,不经过 u 的父节点所能到达的最小发现时间
         low[u] = min( disc[u],
                       对所有树边 (u, v):low[v],
                       对所有回边 (u, w):disc[w] )

判定桥(割边):对树边 (u, v),若 low[v] > disc[u],则这条边是桥
判定割点:     对树边 (u, v),若 low[v] ≥ disc[u],则 u 是割点(v 子树无法绕回 u 的祖先)
               特例:DFS 树的根节点在有多于一个子树时才是割点

直观解释:low[v] > disc[u] 表示 v 及其后代没有任何回边能绕到 u 或 u 的祖先,因此删去边 (u, v) 后 v 的子树与其余部分断开;low[v] ≥ disc[u] 表示 v 的子树最多只能绕回 u,一旦 u 被移除即断开。全部过程在一次 DFS 内完成,复杂度 O(n + m)。

由这两个判定可以派生出两类分解:

  • 边双连通分量:删除任意一条边都不改变连通性的极大子图。等价于把全部桥删去后剩下的连通分量,可以用「DFS 中把边压栈、遇到桥时弹出成组」的方式一次性求出。
  • 点双连通分量:删除任意一个顶点都不改变连通性的极大子图。等价于无割点的极大子图,通常用「DFS 中把边压栈、遇到割点判定成立时弹出成组」求出。

三类工程用途:网络可靠性(桥对应单链路、割点对应单点设备,是单点清单的直接来源,见 linux: 高可用与集群);服务依赖的脆弱点识别(某个共享基础服务是割点,它的故障会切断多条依赖路径);图的结构分解(把大图按双连通分量切成小块,分块处理后再合并,或用于生成更小的测试用例)。

2.5.6 连通性维护与并查集

前述算法回答的是「当前这张静态图的连通情况」。若图会随时间变化,问题变为动态连通性:持续加入边(可能还有删除边),并随时回答「两个顶点是否连通」。

**只加边(增量)**的场景可以用并查集(不相交集合)做到接近常数时间:

find(x):带路径压缩,返回 x 所在集合的代表元素
union(x, y):按秩(或按大小)合并两个集合

连通判断:find(x) == find(y)
加入边 (u, v):union(u, v)

两种优化叠加后,n 次操作的摊还代价为 O(α(n)),α 为反阿克曼函数,在可想象的规模下不超过 4。并查集的适用条件是边的加入单调递增:一旦两个顶点连通,后续只可能保持连通,因此「集合只合并不拆分」这一结构不变量成立。典型用法是 Kruskal 最小生成树、离线批量建图后的连通性查询、按时间顺序处理边的「最早何时连通」类问题。并查集的结构、路径压缩与按秩合并、以及带权与种类并查集见 线段树与并查集。

不适用并查集的两种情形:

  1. 需要删除边。并查集不支持拆分,必须改用其他结构。当删除占比较小或操作可离线处理时,常见做法是把操作序列反向处理(删除变为加入),或按时间分块重建。
  2. 需要具体的路径或距离。并查集只回答「是否连通」,不给出路径。需要路径时必须维护遍历结构,或使用生成树的邻接关系配合 LCA 之类的结构。以边权为条件、需要「在某个阈值下连通」的查询则属于最小生成树与瓶颈路径问题,由 Kruskal 或 Kruskal 重构树处理。

2.6 图与其建模

算法与结构的选择之前还有一步更重要的决策:把业务问题抽象成图时,点是什么、边是什么。这一步决定的不只是代码结构,还直接决定了复杂度。

四类常见建模方式及其代价:

业务形态 顶点 边 代价量级与注意点
依赖与任务调度 任务、模块、编译单元 依赖关系(u → v 表示 u 先于 v) O(n + m);注意依赖方向的定义必须全图统一,反之会将拓扑序整体倒置
网络与拓扑 主机、路由器、服务实例 物理链路、网络可达、调用关系 边权可能取时延、带宽、成本,需区分「拓扑距离」与「业务距离」
社交与推荐 用户、物品、标签 关注、点击、共现、购买 二分图(用户—物品)或多部图;边数可能达 n² 量级,必须稀疏化后再处理
状态空间搜索 一个完整的状态 一次合法状态转移 状态数通常指数级,不能显式建图;只在展开时按规则生成邻居(隐式图)

建模阶段的三个判断点:

  1. 点与边的选择决定了规模。同一问题有多种建模方式。以「最短编辑次数」为例,把每个中间字符串作为顶点会得到一个可能指数级的状态图;把问题转化为「序列上的对齐问题」用动态规划,则规模与两个序列长度之积成正比。能用更小规模的点集表达同一关系,就应优先选择它。
  2. 显式图与隐式图的取舍。状态空间图通常只给出「生成邻居」的规则而不预先把图建出来,代价是每次访问一个顶点都要现场计算邻居(可能比查表慢,且可能重复生成同一状态),收益是空间从 O(状态数) 降到 O(已访问集)。这类实现必须配一个高效的访问标记结构,通常用哈希集合或位图,见 散列表 与 位图与布隆过滤器。
  3. 边权与边属性的选择决定了算法族。无权的可达性与最短路径用 BFS;非负权最短路用 Dijkstra;含负权的用 Bellman-Ford 或 SPFA;只关心「通过与否」的容量问题用最大流。把无权问题误建模为带权(或反之),会使算法复杂度上升一个量级,也可能让本可 O(n + m) 的问题变成 O(m log n)。

一个常被忽略的建模陷阱是把「点」定得太细或太粗。点太细会导致顶点数爆炸(例如把每一次请求作为一个顶点),点太粗会使边丢失必要语义(例如把整个服务作为一个顶点,就无法刻画服务内部的调用链割点)。建模的原则是:顶点应当对应「有独立状态的实体」,边应当对应「实体之间可验证的关系」,而顶点规模必须在内存与时间预算之内。


三、实现

3.1 存储实现要点

3.1.1 邻接表的容器选择

Java 中表达邻接表有三种常见形式,代价差异明显:

// 形式一:容器数组(最直观,对象开销最大)
List<List<Integer>> adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
adj.get(u).add(v);                          // 无向图对 (u, v) 与 (v, u) 各调用一次

// 形式二:平行数组 + 前向星(无额外对象,遍历缓存友好)
int[] head = new int[n];
Arrays.fill(head, -1);
int[] to = new int[2 * m];                  // 无向图每条边两条弧
int[] nxt = new int[2 * m];
int cnt = 0;
// addEdge(u, v):to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++;

// 形式三:CSR(构造后 neighbor 区间连续,遍历最快)
int[] offset = new int[n + 1];
int[] target = new int[2 * m];

选择依据:

  • 形式一适合原型与数据量不大的场景,代码可读性最好。代价是每个顶点一个 ArrayList 对象(含对象头与内部数组引用)、每个元素一个装箱 Integer(约 16 字节),以及节点分散导致的缓存未命中。装箱与数组扩容的代价见 Java 集合框架实现原理。
  • 形式二适合大规模图与性能敏感场景,全部数据在连续数组中,只需 O(n + m) 个基本类型空间,且增边为 O(1) 头插,可动态扩展。
  • 形式三适合一次性建图、多次查询的场景,邻居区间连续使遍历的缓存局部性最好,代价是构造需要两遍扫描,且建好后增删边困难。

3.1.2 邻居的去重与排序

同一对顶点之间出现多条边(重边)时,不同算法的处理方式不同:

场景 处理方式
判边与判环 必须能区分重边与环,或直接去重后处理
度与入度统计 重边会计入度,若语义上「多重连接」有意义则保留,否则去重
最短路与 BFS 重边不影响正确性,但会增加无效展开次数
拓扑排序 重边会使入度偏大,出现「能到达却永远不入队」的假环现象,必须去重

去重的两种做法:在插入时检查(小规模用线性查找,大规模在邻接表之外再维护一个哈希集合做「边是否已存在」的索引,见 散列表);或在建图完成后对每个顶点的邻居排序并去除相邻重复项,整体代价 O(m log m) 或按度分布加权的 O(Σ deg log deg)。

排序同时带来第二个收益:遍历结果的确定性。未排序的邻接表使 DFS 与 BFS 的访问次序依赖插入顺序,同一份逻辑图在不同构造路径下会产生不同的拓扑序、不同的分量编号、不同的路径选择。需要在测试中断言结果、在线上复现问题、或要求输出字典序最小时,必须显式排序。

for (List<Integer> neighbors : adj) {
    Collections.sort(neighbors);
    // 去重:或用一个写指针原地压缩,避免额外容器
}

3.1.3 有向图的入边表

有向图算法中大量操作需要「枚举指向 v 的边」,仅维护出边邻接表时这类操作要扫描全图。常见需要入边的算法:

  • Kahn 拓扑排序需要统计并递减入度(统计入度只需一次扫描全边,但若还要在环出现时定位回路,入边表更方便)。
  • 反向 BFS(求「哪些顶点能到达目标」、故障影响面的反向追溯)需要沿入边反向展开。
  • 双向 BFS 需要两侧同时展开,反向一侧必须能沿入边前进。
  • Kosaraju 强连通分量算法的第二遍 DFS 在反向图上进行。

做法是同时维护出边邻接表与入边邻接表,空间代价从 O(n + m) 变为 O(n + 2m)(常数倍),换取消除了 O(n·m) 的反向扫描。若内存紧张且只需要度数而不需要邻居,可只维护入度计数数组(4n 字节)。

3.1.4 带权边的表示

三种方案的取舍:

// 方案一:平行数组,无对象开销(推荐用于大规模图)
int[] to;   long[] w;   int[] nxt;   int[] head;

// 方案二:编码为单个 long(权重位数受限时)
long packed = ((long) v << 32) | (weight & 0xffffffffL);
int v = (int) (packed >>> 32);

// 方案三:对象(可读性最好,但每边多一个对象与一次间接寻址)
record Edge(int from, int to, int weight) {}
List<Edge>[] adj;

需要注意权重类型与哨兵值的配合:用 int 表示无限大时,松弛运算 dist[u] + w 可能溢出,必须显式判断或改用 long;用 0 表示「无边」时无法表达权重为 0 的合法边。哨兵值的选择必须与权重的取值范围一起确定,这类错误只在含极值权重的输入上出现。

3.1.5 大规模图的内存估算

以 n 个顶点、m 条边的无向图为例(无向图存储两条弧,记为 2m)。

邻接矩阵(boolean[][]):       n² 字节
邻接矩阵(位图压缩):          n² / 8 字节
邻接表(容器 + 装箱):         约 (40 + 4·avgDeg) · n  +  16 · 2m  字节
                                (每个 ArrayList 对象约 40 字节、每个装箱 Integer 约 16 字节)
邻接表(平行数组 / 前向星):    (4·n) + (4 + 4 + 8) · 2m  字节  ≈ 4n + 32m
CSR(不带权):                 4·(n + 1) + 4 · 2m  字节
CSR(带 long 权重):           4·(n + 1) + (4 + 8) · 2m  字节

n = 10⁵、m = 10⁶ 时:
    邻接矩阵(位图)    1.25 GB
    邻接表(容器 + 装箱)约 4 MB + 32 MB = 36 MB
    前向星(不带权)    约 0.4 MB + 16 MB = 16.4 MB
    CSR(带权)         约 0.4 MB + 24 MB = 24.4 MB

估算顺序应当是:先算 n²,再算 m,最后算两者的倍数。若 n² 字节已经在内存预算之外,邻接矩阵直接排除;若 n + m 也在预算之外,则需要重新审视建模(减少顶点、稀疏化边、改分块或外存处理),而不是换一种表示继续尝试。

3.2 遍历实现要点

3.2.1 迭代 DFS 的入栈时机

这是迭代 DFS 最容易出错的一点。两种写法的差别只在标记发生的时刻:

写法 A(错误):弹栈时标记
    push(s)
    while 栈非空:
        u = pop()
        if visited[u]:continue           // 补救式判断
        visited[u] = true
        for each 邻居 v:
            if not visited[v]:push(v)    // 此时 v 可能已被压入多次

写法 B(正确):压栈时标记
    visited[s] = true; push(s)
    while 栈非空:
        u = pop()
        for each 邻居 v:
            if not visited[v]:
                visited[v] = true         // 立即标记
                push(v)

写法 A 的问题在于同一顶点会被多个已访问邻居重复压入,栈的峰值容量从 O(n) 膨胀到 O(m),在大规模图上表现为内存占用异常增长,同时每个顶点被弹出多次导致常数显著上升。写法 A 中额外的 visited[u] 判断只保证正确性(不会重复处理),不能避免重复入栈。

第二种易错点是访问时刻与递归语义的偏差:写法 B 中「访问 u」发生在弹出时,而邻居的压栈顺序与递归展开顺序相反。若算法依赖前序/后序语义(例如构造 DFS 树的时间戳、求拓扑序的完成时间),必须:

  • 要么在压栈时按邻接表顺序逆序压入邻居,使弹出顺序与递归一致;
  • 要么在栈中保存「顶点 + 阶段标记」的二元组,在第一次弹出时压回自身与邻居、第二次弹出时执行后序逻辑。

3.2.2 BFS 的入队标记时机

与 DFS 对称但更关键,因为 BFS 的重复入队会直接破坏距离信息的正确性:

正确做法:出队时检查邻居 v 是否未访问,若未访问则「先标记、再赋距离、后入队」
错误做法:在出队时才标记 visited,入队时不标记

后果:同一顶点可能被多个同层邻居重复入队,
      虽然距离值仍然正确(第一次入队时已赋值),但队列长度可能膨胀到 O(m),
      且按层处理时同一层的顶点数统计出错(层内出现重复顶点)。

用距离数组(dist[v] == -1 表示未访问)代替布尔标记可以让「标记」与「赋距离」合并为一次写入,既避免了两个数组的同步问题,也天然阻止了重复入队。

第三点是层次划分时的顺序:记录 size = queue.size() 必须在本层开始处理之前,且本层的全部入队操作都发生在处理过程中,因此入队的是下一层的顶点。若把循环条件直接写成「队列非空」而不固定层大小,不同层的顶点会在输出中混杂。

3.2.3 层次信息的记录方式

三种方式对应不同需求:

方式 实现 适用
距离数组 dist[v] = dist[u] + 1 需要每个顶点的距离(最短路问题)
层大小计数 每轮开始记录 queue.size() 只关心「第几层有哪些顶点」
分层标记 队列中保存 (顶点, 层号) 二元组 层号与顶点数量的对应关系不稳定,或需要按层做不同处理

层号信息还有一项隐含用途:限制搜索深度(只展开 d 层以内的顶点)与剪枝(距离超过当前最优解时停止展开)。这类「有界 BFS」在状态空间搜索中很常见,代价是把「一次遍历」变为「一次局部遍历」,收益是跳过大量无关状态。

3.2.4 多源 BFS

多源 BFS 把多个起点同时放入队列(距离均为 0),随后按普通 BFS 展开。它求解的是「每个顶点到最近起点的距离」,等价于在图上增加一个虚拟源点、把它与全部真实起点相连后做单源 BFS。

void multiSourceBfs(List<List<Integer>> adj, int[] sources, int[] dist) {
    Arrays.fill(dist, -1);
    Queue<Integer> queue = new ArrayDeque<>();
    for (int s : sources) {
        if (dist[s] == -1) {                  // 起点可能重复,需判重
            dist[s] = 0;
            queue.offer(s);
        }
    }
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
}

复杂度与单源 BFS 相同,为 O(n + m),而逐源做 n 次 BFS 的代价是 O(k·(n + m))。典型用途是「一片区域到最近出口的距离」「多个仓库到全部网点的时间」「按多个热点扩散的影响范围」。使用时有两处必须注意:起点集合去重(重复起点会导致同一顶点被压入多次)与空起点集合的处理(此时全部距离保持 −1,算法立即结束,调用方需要能区分「不可达」与「没有起点」两种结果)。

3.3 典型实现

3.3.1 拓扑排序与环检测

/** Kahn 入度法。返回拓扑序;若存在环,返回的列表长度小于 n。 */
static List<Integer> topologicalSort(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : adj.get(u)) {
            indeg[v]++;                                    // 统计入度
        }
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int v = 0; v < n; v++) {
        if (indeg[v] == 0) {
            queue.offer(v);                                // 入度为 0 的顶点可先执行
        }
    }
    List<Integer> order = new ArrayList<>(n);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) {                         // 前置条件全部满足
                queue.offer(v);
            }
        }
    }
    return order;                                          // order.size() < n 表示存在环
}

/** 在 Kahn 法判定存在环后,从剩余顶点中定位一条具体回路。 */
static List<Integer> findCycle(int n, List<List<Integer>> adj, int[] indeg) {
    int[] state = new int[n];                              // 0 未访问、1 在当前 DFS 路径上、2 已完成
    int[] cursor = new int[n];                             // 每个顶点已扫描到的邻居下标
    int[] path = new int[n];
    int[] pos = new int[n];                                // 顶点在路径数组中的下标
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {
        if (indeg[s] == 0 || state[s] != 0) {
            continue;                                      // 入度为 0 的顶点不可能在环上
        }
        int depth = 0;
        state[s] = 1;
        pos[s] = depth;
        path[depth++] = s;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.peek();
            List<Integer> neighbors = adj.get(u);
            boolean advanced = false;
            while (cursor[u] < neighbors.size()) {
                int v = neighbors.get(cursor[u]++);
                if (indeg[v] == 0) {
                    continue;                              // 已由拓扑序输出的顶点不在环上
                }
                if (state[v] == 1) {                       // 回边:路径上 pos[v] 到 u 即一条回路
                    List<Integer> cycle = new ArrayList<>();
                    for (int i = pos[v]; i < depth; i++) {
                        cycle.add(path[i]);
                    }
                    return cycle;
                }
                if (state[v] == 0) {
                    state[v] = 1;
                    pos[v] = depth;
                    path[depth++] = v;
                    stack.push(v);
                    advanced = true;
                    break;                                 // 先深入新发现的顶点
                }
            }
            if (!advanced) {
                state[u] = 2;                              // 邻居全部处理完毕
                depth--;
                stack.pop();
            }
        }
    }
    return List.of();
}
/** DFS 完成序法。三色状态同时完成环检测。 */
static List<Integer> topologicalSortByDfs(int n, List<List<Integer>> adj) {
    int[] color = new int[n];                              // 0 白、1 灰、2 黑
    List<Integer> result = new ArrayList<>(n);
    boolean[] hasCycle = {false};

    for (int v = 0; v < n && !hasCycle[0]; v++) {
        if (color[v] == 0) {
            dfsOrder(adj, v, color, result, hasCycle);
        }
    }
    if (hasCycle[0]) {
        return List.of();                                  // 有环时拓扑序不存在
    }
    Collections.reverse(result);                           // 完成序的逆序即拓扑序
    return result;
}

private static void dfsOrder(List<List<Integer>> adj, int u, int[] color,
                             List<Integer> result, boolean[] hasCycle) {
    color[u] = 1;                                          // 灰色:在当前递归栈上
    for (int v : adj.get(u)) {
        if (hasCycle[0]) {
            return;
        }
        if (color[v] == 1) {
            hasCycle[0] = true;                            // 回边 → 存在环
            return;
        }
        if (color[v] == 0) {
            dfsOrder(adj, v, color, result, hasCycle);
        }
    }
    color[u] = 2;                                          // 黑色:子树处理完毕
    result.add(u);                                         // 后序位置记录完成顺序
}

复杂度:两种写法都是 O(n + m)(每次检查一条边、每个顶点进入一次),空间 O(n)(入度数组或颜色数组,加上队列或递归栈)。递归版在深图上需注意栈深度,可改用显式栈保存 (顶点, 邻居游标) 二元组。

3.3.2 二分图染色判定

/** 染色法判定二分图。返回 false 表示存在奇环,即不是二分图。 */
static boolean isBipartite(int n, List<List<Integer>> adj) {
    int[] color = new int[n];
    Arrays.fill(color, -1);                                // −1 未染色,0 与 1 为两种颜色
    for (int s = 0; s < n; s++) {
        if (color[s] != -1) {
            continue;                                      // 非连通图必须逐分量处理
        }
        color[s] = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];               // 邻点取反色
                    stack.push(v);
                } else if (color[v] == color[u]) {
                    return false;                          // 同色相邻 → 奇环
                }
            }
        }
    }
    return true;
}

复杂度 O(n + m)。要点有两条:必须遍历全部顶点而非只从 0 号顶点出发(否则非连通图会漏掉分量内的冲突);染色与入栈必须同时进行(先入栈后染色的写法会让同一顶点被多次以不同颜色压入)。

3.3.3 连通分量统计

/** 无向图连通分量计数,同时输出每个顶点的分量编号。 */
static int countComponents(int n, List<List<Integer>> adj, int[] comp) {
    Arrays.fill(comp, -1);
    int count = 0;
    for (int s = 0; s < n; s++) {
        if (comp[s] != -1) {
            continue;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        comp[s] = count;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (comp[v] == -1) {
                    comp[v] = count;
                    stack.push(v);
                }
            }
        }
        count++;
    }
    return count;
}

复杂度 O(n + m)。把 BFS 换成队列实现即得到分量内按层次展开的版本,两者对分量划分的结果相同,只是访问次序不同。若图的边是随时间增量加入的,应改用并查集,见 2.5.6 节。

3.3.4 无权图最短路径

/** 无权图单源最短路径,同时给出前驱用于还原路径。 */
static void shortestPath(int n, List<List<Integer>> adj, int s, int[] dist, int[] pred) {
    Arrays.fill(dist, -1);
    Arrays.fill(pred, -1);
    Deque<Integer> queue = new ArrayDeque<>();
    dist[s] = 0;
    queue.offer(s);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;                     // 首次到达即最短
                pred[v] = u;
                queue.offer(v);                            // 与标记同时完成
            }
        }
    }
}

/** 由前驱数组还原 s 到 t 的路径;不可达时返回空列表。 */
static List<Integer> buildPath(int[] pred, int s, int t) {
    LinkedList<Integer> path = new LinkedList<>();
    for (int cur = t; cur != -1; cur = pred[cur]) {
        path.addFirst(cur);
        if (cur == s) {
            return path;
        }
    }
    return List.of();                                      // t 不可达(或 t 不在本次遍历范围内)
}

复杂度 O(n + m);路径还原为 O(路径长度)。一处细节:还原时若从 t 沿前驱回溯到 −1 仍未遇到 s,说明 t 不可达,必须显式返回空结果,而不是返回一条从某个根开始的半截路径。

3.4 复杂度与实测

3.4.1 不同表示下的复杂度对照

操作 邻接矩阵 邻接表 / 前向星 CSR 边集数组
DFS / BFS 全图遍历 O(n²) O(n + m) O(n + m) 不适用
判断 (u, v) 相邻 O(1) O(deg(u)) O(log deg(u))(有序时) O(m)
统计全部顶点的度 O(n²) O(n + m) O(n + m) O(m) + O(n)
枚举某个顶点的邻居 O(n) O(deg(v)) O(deg(v)) O(m)
按权重排序全部边 O(n² + m log m) O(m log m) O(m log m) O(m log m)
空间 O(n²) O(n + m) O(n + m) O(m)

对照的读法有三条:

  1. 邻接矩阵与邻接表的差距集中在「枚举邻居」。稠密图中 deg(v) ≈ n,两者同阶;稀疏图中 deg(v) 可能只有个位数,两者相差 n / deg(v) 倍,在 n = 10⁵、平均度为 4 时相差约 2.5 × 10⁴ 倍。
  2. O(n + m) 与 O(n²) 的对比在稀疏图上才有意义。若 m 本身就接近 n²/2,O(n + m) 与 O(n²) 同阶,此时矩阵的常数优势(连续寻址、无间接跳转)可能使实测结果反过来。
  3. 复杂度相同时要比较常数与缓存行为。邻接表(容器 + 装箱)与前向星都是 O(n + m),但后者的实测遍历耗时通常明显更低,原因是邻居连续存放、无装箱、无对象解引用。量级相同或接近时必须以实测为准,方法见 JMH 微基准测试。

3.4.2 稀疏与稠密场景的选择依据

判断条件 推荐表示 依据
n ≤ 10³ 且 m 接近 n²/2 邻接矩阵 判边 O(1),遍历代价同阶,实现最简单
n ≥ 10⁴ 且 m = O(n) 邻接表 / 前向星 / CSR 空间 O(n + m),遍历 O(n + m)
大量重复判边或查边权 矩阵,或邻接表 + 哈希索引 把 O(deg) 降为 O(1) 或期望 O(1)
只按边处理的算法(Kruskal、Bellman-Ford) 边集数组 无需邻接关系,天然按边迭代
一次性建图、多次遍历 CSR 邻居区间连续,遍历缓存最优
边会频繁增删 前向星或容器邻接表 CSR 的区间结构不支持低成本增删
n 极大且只需可达性 位图或布隆过滤器做访问标记,图本身不显式构建 访问集合的空间由状态数决定,见 位图与布隆过滤器

3.4.3 大规模图的性能与内存测量方法

遍历的性能结论必须落到测量上,观测指标有三类,缺一不可。

时间指标。 记录遍历总耗时随 n、m 的变化曲线,至少取三个规模点,判断实测增长是否符合 O(n + m)。若出现超线性增长,先检查是否有以下三类隐藏代价:邻接表的邻居枚举在内部做了线性查找(判重未用哈希);每次访问顶点都重新构造邻居集合;按层处理时反复遍历队列(queue.size() 之后又对队列做整体扫描)。

内存指标。 同时记录建图完成后的堆占用与遍历期间的峰值。建图阶段的内存估算见 3.1.5 节;遍历阶段的峰值来自三处:访问标记(布尔数组 n 字节,或哈希集合的按需膨胀)、前驱与距离数组(8n 字节)、以及队列或栈(BFS 的队列峰值等于最大层宽度,DFS 的栈峰值等于最长路径)。使用容器实现的邻接表时,装箱对象的数量也需计入。

对比基准。 需要比较两种表示或两种遍历实现时,按微基准的要求固定条件:同一数据集、同一 JVM 参数、固定堆与回收器、分离预热与测量阶段、覆盖随机图与最坏形态图(路径图、星形图、完全图、二分图)两类输入。随机图会掩盖缓存局部性与分支预测的差异,而最坏形态图(例如长链路径图)会放大递归深度与栈空间的问题,两者都不可省略。方法与干扰控制原则见 JMH 微基准测试。

三处容易误判的地方:

  1. 把「建图耗时」与「遍历耗时」混在一起统计。建图涉及大量随机写入与前缀和计算,其耗时特征与遍历完全不同;两者必须分别计时。
  2. 用总耗时除以顶点数作为「单顶点代价」。稀疏图中各顶点的度差异可能达数个数量级,平均值掩盖了热点;应按度分布分组统计,或直接观察长尾顶点。
  3. 忽略图数据本身的分布。真实图(社交网络、网页链接、调用关系)通常具有幂律度分布,少数顶点连接了大量邻居,这与随机图的实测结果差异显著,选型与调优不能基于随机图结论。

3.5 工程应用

3.5.1 任务与依赖编排

构建系统是最直接的例子:源文件与目标文件、任务与前置任务构成一张有向无环图,构建过程即这张图的拓扑排序加并行执行。实现要点有四条:

  • 依赖图的方向必须全图统一。常见约定是「u → v 表示 u 依赖 v」或「u → v 表示 u 完成后才能执行 v」,两种约定会使入度的语义完全相反。混用会导致「全部顶点入度非零」或「顺序整体倒置」两类缺陷。
  • 环必须被检出并报告具体回路。依赖环意味着无法确定执行顺序,且这类缺陷在依赖图规模变大后必然出现;只报告「存在环」而不给出回路会让排查成本急剧上升,见 3.3.1 节的回路定位实现。
  • 按层出队对应并行调度分批。Kahn 法中同一批入度归零的顶点之间没有依赖关系,可以并行执行;这一分批结果直接对应并行构建的调度批次。
  • 增量构建依赖反向查询。判断「某个文件变更会影响哪些产物」需要沿依赖方向反向展开,因此除了出边邻接表还需要入边表(见 3.1.3 节)。构建系统与持续集成的流水线组织见 Java 构建与 CI 流水线。

3.5.2 服务依赖拓扑与故障影响面分析

把服务实例作为顶点、调用关系作为有向边,可以得到一张服务依赖图,它支撑三类分析:

  • 故障影响面(爆炸半径)。某个服务失效后,哪些服务会受影响,等价于在反向图上从该顶点出发做一次可达性遍历。结果集合的规模即影响面大小,可作为告警定级与降级决策依据。
  • 单点识别。割点与桥直接对应「失效会造成拓扑断裂」的顶点与链路,是单点清单的图论依据。高可用架构中单点故障的识别方法见 linux: 高可用与集群。
  • 依赖环与循环调用。服务间的环形调用是常见的架构缺陷,除了造成级联故障风险,还使「启动顺序」「降级顺序」无法确定,检测方式与任务依赖图的环检测相同。

使用这类图时必须明确边的语义:「调用」与「数据流向」是两种不同的边,得到的可达集合也不相同。图上还应附加属性(调用量、时延、错误率),否则拓扑分析的结论无法与容量和性能问题挂钩。

3.5.3 网络拓扑与路由

网络设备的连接关系构成无向图(物理链路)与有向图(路由可达性)。图论概念在这一领域的对应关系:

图论概念 网络含义
连通分量 是否形成网络孤岛、分区
割点 / 桥 单点设备 / 单链路,链路冗余规划的依据
最短路径 路由的最优路径计算(权重取跳数、时延或代价)
生成树 二层网络的环路避免(生成树协议)
最小生成树 以最小成本铺设链路
最大流 / 最小割 链路容量规划与瓶颈链路定位

网络层的配置与连接关系(网卡、网桥、路由及其与图上顶点边的对应)见 linux: 网络。实践中的两点差异:网络图的规模可能达到数万个顶点,且拓扑会随链路状态动态变化(增删边、权值变化),因此需要支持增量的表示与增量重算,而不是每次全图重新计算。

3.5.4 社交关系与推荐

社交关系图是有向图(关注)或无向图(好友)。三类图算法在这一领域被反复使用:

  • 可达性与扩展度。多源 BFS 求「多少个用户处于某个话题的 k 跳范围内」,用于传播范围预估。
  • 连通分量与社区发现。连通分量是最粗粒度的分组;更细的划分(社区发现)在此基础上引入边权与模块度指标。
  • 二分图结构。用户与物品、用户与标签、内容与标签之间天然构成二分图,用于协同过滤的候选生成与冲突检测(例如「同一用户不能同时被分入两个互斥的活动」可转化为二分图着色问题)。

这一领域最主要的问题不是算法本身,而是规模与稀疏化:关系的理论上限是 n²,实际处理时必须先按阈值裁剪(只保留权重最高的若干条边)、或按时间窗口聚焦当前活跃关系,否则内存与计算量都不可接受。

3.5.5 状态空间搜索与路径规划

把状态作为顶点、合法状态转移作为有向边,问题转化为在图上搜索。三类典型算法族与遍历的关系:

  • 无权状态空间:BFS 求最少步数,双向 BFS 在分支因子大时降低指数因子。
  • 带权状态空间:代价不等时用 Dijkstra(按代价出队,需优先队列)或 A*(用启发函数引导展开方向)。优先队列与堆的实现机制见 堆与优先队列。
  • 可行性搜索:只需判断「是否存在解」时用 DFS 加剪枝,通过访问标记集合避免重复展开同一状态。

实现上的三个关键点:状态的编码与去重(访问标记必须能唯一标识状态,编码冲突会造成错误剪枝,见 散列表);状态空间的边界(顶点数可能指数级,必须设置展开上限并明确超限时的行为);搜索方向的代价平衡(双向 BFS 与 A* 的启发函数质量直接决定展开量级)。

3.5.6 访问控制与权限继承

权限模型天然是一个有向图:用户、角色、资源、权限是顶点,「拥有」「继承」「包含」是边。

  • 角色继承。角色之间的包含关系构成有向图,判断某用户是否拥有某权限等价于从用户的角色出发做一次可达性遍历。继承关系若出现环,会造成权限判定的逻辑混乱与递归深度问题,必须检测并拒绝。
  • 资源层级与权限传播。目录树、组织结构、资源分组构成树(或带共享节点的有向图),权限从上层向下层传播,等价于在图上做自顶向下的遍历并合并沿途的授权规则。
  • 冲突与互斥。职责分离要求「某些权限不能同时授予同一个主体」,把「互斥对」建模为边并按二分图判定,可以一次性检查出冲突集合。

这类图的特点是规模不大但变更频繁,且要求判定结果可解释(需要说明权限是从哪条路径继承而来的),因此通常需要同时保存遍历路径而不只是连通性结论。

3.6 常见问题与排查

现象 可能原因 验证与处置
大规模图上抛 StackOverflowError,异常栈中 DFS 方法重复成百上千层 递归 DFS 的深度等于最长路径长度,长链图上达 O(n) 统计图的直径或最长路径;把递归改为显式栈迭代;显式栈的标记必须放在压栈时(见 3.2.1 节)
遍历无法终止,或同一顶点被反复访问 访问标记缺失、标记时刻不对(弹栈时标记)、或标记数组未初始化 检查标记是否在「发现顶点」的同一时刻写入;在 BFS 中用距离数组代替布尔数组合并两次写入;打印已访问计数与顶点数对比
迭代版 DFS 内存占用远高于预期 弹栈时标记导致同一顶点被重复压入,栈峰值达 O(m) 改为压栈时标记;观察栈峰值与 n、m 的关系(应为 O(n) 而非 O(m))
BFS 输出的层内出现重复顶点,或层数划分错乱 入队时未标记,同一顶点被多个同层邻居重复入队;或层大小在循环中被重新读取 在入队处完成标记与距离赋值;层大小在本层处理前固定为局部变量
拓扑排序结果缺少顶点 图中有环(剩余顶点入度均不为 0);或统计入度时对重边重复计数 断言输出长度等于 n;对邻接表去重后再统计入度;按 3.3.1 节定位具体回路并报告
拓扑序整体倒置 依赖边的方向约定与算法假设不一致 明确「u → v 表示 u 先于 v」还是「u 依赖 v」;用一条已知依赖关系做断言测试
割点或桥的判定在根节点处出错 DFS 树根节点的割点判据与其他顶点不同(子树数大于 1 才是割点) 对根节点单独判断子树数量;用小规模手工可算的图(三角加悬挂点)验证
环检测把重边或自环误判为环 无向图用「已访问且非父节点」判定时会漏掉重边与自环的特殊情形 改用边编号排除进入边,或改用并查集逐边检查;显式处理 u == v 的自环
无权图最短路结果错误 在有向图上沿入边方向做了 BFS;或距离数组初始化不当导致未访问顶点被当作距离 0 确认展开方向与边方向一致;未访问标记用 −1 并与距离 0 区分;对不可达顶点显式返回空路径
稀疏图误用邻接矩阵,内存不足或遍历极慢 未估算 n² 字节是否在预算内;未观察枚举邻居的代价 按 3.1.5 节先估算 n² 与 n + m,再决定表示;遍历耗时应与 n + m 成正比而非与 n² 成正比
内存占用随遍历推进持续增长 访问标记用哈希集合且顶点数极大;或前驱记录保存了对象引用而非编号 改用基本类型数组或位图压缩;前驱与距离统一保存下标而非顶点对象
并查集在「删除边」场景给出错误结论 并查集只支持合并,不支持拆分 改为反向处理操作序列(把删除转为加入),或按时间分块重建结构

排查顺序。 面对「遍历结果异常」或「遍历耗时异常」时,按以下顺序推进:

  1. 确认图的规模与形态:n、m 的实际取值,度分布是否长尾,是否存在长链、孤立点、自环、重边。形态决定了很多结论(递归深度、队列峰值、是否稀疏)。
  2. 确认边的方向与语义:出边还是入边,权重含义,是否存在双向记录。方向错误会同时导致拓扑序倒置与可达性判断反转。
  3. 确认标记与距离的一致性:标记在哪里写入、距离在哪里赋值,两者是否在同一次操作中完成;用一个五到十个顶点的手工图逐步打印标记与队列或栈的状态。
  4. 确认遍历的终止条件:非连通图是否遍历了全部顶点(外层循环是否完整),单源遍历是否只覆盖了该源所在的分量。
  5. 分别计时建图与遍历:若耗时异常,先排除建图阶段(排序、去重、哈希索引构建)的贡献。
  6. 核对复杂度口径:遍历耗时应当与 n + m 成正比。若与 n² 成正比,检查是否误用了邻接矩阵或在大规模图上保留了矩阵式的判边逻辑。

3.7 检查清单:图的建模与实现自检项

有向性判定。

  • 每条边是否明确方向?有向图中「u 依赖 v」与「u 先于 v」是否在全图统一?
  • 需要反向查询的算法(反向可达、双向 BFS、Kosaraju)是否有入边表或反向图?
  • 无向图的每条边是否在邻接表中记录了两次(或使用了对称的存储约定)?
  • 是否存在环?业务上是否允许环?若不允许,是否在构建期就检测并拒绝了?

权重与边界。

  • 边的权重类型与取值范围是什么?无限大与「无边」的哨兵值是否与合法权重冲突?
  • 松弛运算是否存在溢出风险?是否需要 long?
  • 权重为 0 的边是否被当作「无边」处理?
  • 自环与重边是否显式处理?去重发生在哪一步?
  • 孤立顶点是否保留?顶点编号是否连续(非连续时会多出无效顶点与空邻接表)?

规模与内存预算。

  • n 与 m 的实际上界是多少?是否按 n² 与 n + m 做过内存估算?
  • 图的形态是稀疏还是稠密?表示方法与形态是否匹配?
  • 遍历所需的辅助空间(标记、距离、前驱、队列或栈)是否已计入预算?
  • 递归深度是否可能与 n 同阶?是否已评估栈溢出风险并准备了迭代实现?
  • 最坏形态(路径图、星形图、完全二分图)是否被纳入测试与压测?

遍历正确性。

  • 访问标记是否在「发现顶点」的同一时刻写入?
  • 非连通图的外层循环是否遍历了全部顶点?
  • 有向图的环检测是否使用了三态标记(而非无向图的父节点排除法)?
  • 拓扑排序是否断言了输出长度等于顶点数?
  • 无法排序或有环时,是否给出了具体回路或剩余顶点集合作为诊断信息?
  • BFS 的层次划分是否在层内处理前固定了层大小?
  • 双源或多源遍历的起点集合是否去重?

结果与可复现性。

  • 邻居是否排序?是否需要保证输出次序稳定(可复现、可断言)?
  • 多种合法答案时(拓扑序、分量编号、最短路径的选择),是否接受任意合法解,还是要求特定规则(字典序最小)?
  • 复杂度结论是否说明了 n 与 m 的口径,并注明所用表示方法的前提?
  • 性能结论是否带测量条件(规模、图形态、表示方法、JVM 参数),是否避免无条件的最优性表述?

四、总结

定位。 图把线性结构与树的关系约束进一步放宽:一个顶点可以有多个前驱与多个后继,路径不再唯一,回路成为可能。放宽带来的表达力覆盖了依赖关系、网络结构与状态转移三类普遍形态;代价是必须显式选择一种表示方法,并把连通性、可达性、顺序这些结论交给遍历来回答。图是一种抽象数据类型,邻接矩阵、邻接表、边集数组是它的不同存储实现,这一层次关系见 抽象数据类型(ADT)。

概念。 有向与无向、带权与无权决定了可选算法族;度、入度、出度与边数的关系(无向图 Σ deg = 2m,有向图 Σ 出度 = Σ 入度 = m)提供了实现的校验断言;连通、强连通与连通分量刻画可达性;稠密与稀疏(m 与 n² 的比值)决定表示方法;自环与重边会影响判环、去重与入度统计;二分图等价于不含奇环,也等价于可二染色。

表示。 邻接矩阵以 O(n²) 空间换取判边 O(1),代价是枚举邻居与度无关地为 O(n),适合稠密与小规模图;邻接表以 O(n + m) 空间把枚举邻居做成 O(deg),是稀疏图的默认选择;边集数组空间最小,适合按边处理的算法(Kruskal、Bellman-Ford);链式前向星与 CSR 是邻接表的紧凑实现,前者支持增量增边,后者在静态图上给出最好的缓存局部性。选型的三步是:先看 n 与 m 的量级,再看主要操作(枚举邻居还是判边),最后看是否需要动态修改。

深度优先。 DFS 沿路径深入并根据「最近的选择」回退,因此使用栈;递归实现的空间等于最长路径长度,在长链图上可能溢出,改显式栈时必须在压栈时标记,否则会重复入栈、栈峰值从 O(n) 膨胀到 O(m)。邻接表下复杂度 O(n + m),邻接矩阵下 O(n²)。DFS 的副产品是 DFS 树与发现、完成时间戳,后者提供了祖先关系的区间判定、边类型的分类依据(回边等价于环)以及「完成序的逆序是拓扑序」这一结论。

广度优先。 BFS 按发现顺序展开,因此使用队列;同一层的顶点在队列中连续,先固定层大小即可按层处理。无权图上 BFS 给出的距离就是最短路径长度,依据是出队距离的非递减性与「首次到达即最短」;这一性质只在边权相等时成立。双向 BFS 从两端同时展开,把访问量从 b^d 降到约 2·b^(d/2),前提是能够反向展开,并需要处理两侧距离与相差 1 的情形。

应用。 遍历是骨架,派生算法包括:连通分量计数(一次完整遍历)、环检测(无向图用父边排除,有向图必须用三态标记区分回边与横叉边)、二分图染色(一次遍历加颜色冲突检查,非连通图需逐分量处理)、拓扑排序(Kahn 入度法天然给出并行分批与剩余顶点集合,DFS 完成序法与其他 DFS 副产品合用,环检测需额外状态)、割点与桥与双连通分量(依赖 low 值与发现时间的比较,根节点判据特殊)、以及连通性维护(并查集适用于只加边的增量场景,摊还 O(α(n)),不支持拆分)。建模层面要先确定点与边,再判断显式图与隐式图,最后确认规模在预算之内;点与边的选择直接决定复杂度量级。

实现层面需要落到位的几点。 邻接表的容器选择在可读性与常数因子之间取舍,大规模图应使用平行数组或 CSR;邻居的去重与排序同时解决重复计数与结果可复现两个问题;有向图的反向查询需要入边表;哨兵值必须与权重的取值范围协调;内存估算先从 n² 与 n + m 两个量级入手。遍历实现里,标记与距离必须与「发现顶点」同时写入,BFS 的层大小必须在层内处理前取定,多源 BFS 的起点必须去重。实测时建图与遍历分开计时,覆盖随机图与最坏形态图,按度分布观察热点,并避免用总耗时除以顶点数掩盖长尾。复杂度相同或接近时(邻接表的容器实现与前向星、矩阵与邻接表在稠密图上)必须以实测结论为准,方法见 JMH 微基准测试。

图与其表示的关系可以用一句话概括:图定义了「有哪些关系」,表示方法决定了「以什么代价访问这些关系」,遍历则把所有全局问题归结为一次对全部顶点与边的系统性访问。绝大多数图算法的差异,最终都落在遍历中用哪种容器、维护哪些附加信息这两个选择上。