图由顶点和边构成这个定义简单到可以用一句话说完。但真正开始设计图算法时第一个要面对的问题非常具体如何把一张图放进计算机的内存里不同的存储方式直接决定了后续操作的效率边界甚至影响了算法的设计思路。一、两种基本存储方式设图 G(V,E)G(V,E)∣V∣n∣V∣n∣E∣m∣E∣m。邻接矩阵用一个 n×nn×n 的二维矩阵 AA 存储若顶点 ii 到顶点 jj 有边则 A[i][j]1A[i][j]1或边的权重否则为0。空间开销固定为 Θ(n2)Θ(n2)。查询任意两点之间是否存在边的操作是 O(1)O(1)这是邻接矩阵最突出的优势。但对稀疏图m≪n2m≪n2大量空间被浪费在存储零值上。此外若要枚举一个顶点的所有邻居无论其度数多大都必须扫描整行开销为 Θ(n)Θ(n)。邻接表为每个顶点维护一个链表或动态数组存储与其相邻的顶点。空间开销为 Θ(nm)Θ(nm)对于稀疏图极大地节省了内存。枚举某个顶点的所有邻居只需遍历其链表耗时与该顶点的出度成正比整体遍历全图所有顶点的邻居总计 Θ(nm)Θ(nm)。但查询两点之间是否有边的操作退化到 O(deg⁡(v))O(deg(v))在最坏情况下可能达到 O(n)O(n)。选择哪一个取决于图的稠密程度和典型操作。稠密图中邻接矩阵更简洁大多数实际应用尤其是算法竞赛和工程实现中邻接表因其普适性占主导地位。有些场景会混合使用两者例如用邻接表存图的结构另建一个哈希表加速边存在性查询。二、广度优先搜索层层推进的最短路径广度优先搜索BFS是图遍历中最直观的策略从源点 ss 出发先访问所有距离为1的邻居再访问距离为2的邻居依此类推像水波扩散一样逐层推进。BFS的标准实现依赖一个队列。将源点入队并标记为已访问随后不断从队首取出顶点将其所有未被访问过的邻居入队并标记。每个顶点入队一次、出队一次每条边被检查一次。若图以邻接表存储总时间复杂度为 Θ(nm)Θ(nm)。BFS的核心理论性质是它给出的无权最短路径。对于无权图或所有边权重相同的图定义 δ(s,v)δ(s,v) 为从 ss 到 vv 的最短路径中包含的边数。BFS恰好按 δ(s,v)δ(s,v) 非递减的顺序访问顶点且当算法终止时每个顶点的距离标签 d[v]d[v] 满足 d[v]δ(s,v)d[v]δ(s,v)。证明的关键在于BFS队列中至多同时出现两个连续距离层的顶点这个不变式保证了距离的正确性。BFS还可以输出从 ss 出发的一棵广度优先树——由访问过程中每个顶点被发现时所经由的边组成的树结构。这棵树中从 ss 到任意顶点 vv 的简单路径恰好就是最短路径之一。整个最短路径的信息只需额外存储一个前驱数组 π[v]π[v] 即可完整保存。三、深度优先搜索时间的精细标定深度优先搜索DFS的策略与BFS截然不同沿一条路径尽可能深地探索走到无路可走时再回溯。这个“深入”而非“广撒”的特点使得DFS能够揭示出图的更丰富的结构信息。DFS的经典性质集中体现在括号定理上。对每个顶点记录两个时间戳d[v]d[v] 表示该顶点被发现的时刻涂灰色f[v]f[v] 表示该顶点的所有邻接表被探索完毕的时刻涂黑色。将每个顶点的活跃区间 [d[v],f[v]][d[v],f[v]] 视为时间轴上的一段括号括号定理断言对于任意两个顶点 uu 和 vv它们的活跃区间要么完全不相交要么一个完全包含另一个。这意味着后代的活跃区间严格嵌套在祖先的区间之内——这正是“深度优先”的时间结构体现。括号定理的一个直接推论是边的分类。在DFS过程中当探索一条边 (u,v)(u,v) 时根据顶点 vv 的颜色可将边分为四类树边vv 为白色即 vv 是 uu 在深度优先树中的孩子。后向边vv 为灰色即 vv 是 uu 的祖先此时边指向树中上方形成环。前向边vv 为黑色且 d[u]d[v]d[u]d[v]即 vv 是 uu 的非直接后代。交叉边vv 为黑色且 d[u]d[v]d[u]d[v]即 vv 与 uu 分属不同的子树分支。对于无向图DFS过程中不会出现前向边和交叉边——每一条非树边都是后向边。这是无向图环路检测的基础如果DFS遇到一条指向非父节点且已访问顶点的边必定存在环。四、BFS与DFS的对偶视角BFS和DFS在无权重图中构建了两类截然不同的生成树——前者是“半径极小”的最短路径树后者是“深度极大”的生成树。BFS适合处理与距离相关的问题DFS擅长揭示图的连通结构、环路性质和拓扑顺序。两者均以线性时间运行是所有更复杂图算法的前置步骤。本篇所建立的图遍历框架下一篇将直接扩展为有向无环图的拓扑排序算法以及有向图中强连通分量的分解——这两个问题恰好构成了图论中“线性结构”与“循环结构”分析的一体两面。