当前位置：首页 > news >正文

【算法分析与设计】第11篇：图的表示与遍历算法：BFS与DFS的扩展性质

news 2026/5/26 22:50:34

图由顶点和边构成，这个定义简单到可以用一句话说完。但真正开始设计图算法时，第一个要面对的问题非常具体：如何把一张图放进计算机的内存里？不同的存储方式直接决定了后续操作的效率边界，甚至影响了算法的设计思路。

一、两种基本存储方式

设图 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)。

邻接表：为每个顶点维护一个链表（或动态数组），存储与其相邻的顶点。空间开销为 Θ(n+m)Θ(n+m)，对于稀疏图极大地节省了内存。枚举某个顶点的所有邻居只需遍历其链表，耗时与该顶点的出度成正比，整体遍历全图所有顶点的邻居总计 Θ(n+m)Θ(n+m)。但查询两点之间是否有边的操作退化到 O(deg⁡(v))O(deg(v))，在最坏情况下可能达到 O(n)O(n)。

选择哪一个取决于图的稠密程度和典型操作。稠密图中邻接矩阵更简洁，大多数实际应用（尤其是算法竞赛和工程实现）中，邻接表因其普适性占主导地位。有些场景会混合使用两者，例如用邻接表存图的结构，另建一个哈希表加速边存在性查询。

二、广度优先搜索：层层推进的最短路径

广度优先搜索（BFS）是图遍历中最直观的策略：从源点 ss 出发，先访问所有距离为1的邻居，再访问距离为2的邻居，依此类推，像水波扩散一样逐层推进。

BFS的标准实现依赖一个队列。将源点入队并标记为已访问，随后不断从队首取出顶点，将其所有未被访问过的邻居入队并标记。每个顶点入队一次、出队一次，每条边被检查一次。若图以邻接表存储，总时间复杂度为 Θ(n+m)Θ(n+m)。

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 的颜色可将边分为四类：