1. 概述
在本教程中，我们将讨论关节点（Articulation Points）的概念，以及如何在图中识别它们。关节点是图中非常重要的结构节点，一旦移除，就会导致图的连通分量增加。理解如何识别这些节点，有助于我们评估图结构的鲁棒性和网络的脆弱性。
2. 定义
关节点（Articulation Point） 是指在一个图中，如果移除该顶点及其相连的边后，图将不再连通（即变成两个或更多互不连通的子图），则该顶点被称为关节点。
关节点也常被称为“割点（Cut Vertex）”，是图中连接多个子图的关键桥梁。
我们的目标是找出图中所有的关节点。
3. 示例
我们来看一个无向图的例子：
图 G₁ 包含顶点集合 V = {A, B, C, D, E, F, G} 和边集合 E = {E₁, E₂, E₃, E₄, E₅, E₆, E₇, E₈, E₉}。
如果我们尝试移除顶点 A 及其相连的边 E₁ 和 E₃，图仍然保持连通，因此 A 不是关节点。
但如果我们移除顶点 E 及其相连的边 E₅、E₆、E₇、E₈，则图会被分割为两个连通分量：
- 分量 C₁：顶点集合 {F, G}，边集合 {E₉}
- 分量 C₂：顶点集合 {A, B, C, D}，边集合 {E₁, E₂, E₃, E₄}
这说明 E 的移除导致图断开，因此 E 是一个关节点。
4. 查找所有关节点的算法
我们可以使用基于 DFS（深度优先搜索）的算法来高效地找出图中所有关节点。
algorithm ArticulationPoints(G, s):
// INPUT
// G(V, E) = 一个图，包含顶点 V 和边 E
// s = DFS 的起始顶点
// OUTPUT
// 打印出图中所有的关节点
构建 DFS 树
初始化 Visited, depth, low 数组
Visited[s] <- true
depth[s] <- d
low[s] <- d
for 每个 s 的邻接点 k:
if k 未被访问:
ArticulationPoints(k, d + 1)
low[s] <- min(low[s], low[k])
if low[k] >= depth[s]:
if s 不是根节点 或 其子节点数量 > 1:
print(s + " 是关节点")
✅ 算法核心逻辑
- 构建 DFS 树，记录每个节点的访问顺序（depth）
- 维护 low 数组，表示当前节点通过回边能到达的最小 depth 值
- 如果子节点的 low 值 ≥ 当前节点的 depth 值，则当前节点是关节点
- 根节点只有在有多个子树时才是关节点
⚠️ 注意事项
- 需要处理回边（back edge）的情况
- 必须递归处理每个未访问的邻接点
- 判断根节点是否为关节点时，需要统计其子节点数量
5. 图上演示算法执行过程
我们以图 G₂ 为例，演示算法的执行过程：
✅ 构建 DFS 树
从 A 出发，构建 DFS 树如下：
我们访问顺序是：A → B → D → E → F → D → C
注意：F 到 D 和 C 到 A 的虚线边是回边，不属于 DFS 树。
✅ 计算 depth 和 low 值
| 顶点 | depth | low |
|---|---|---|
| A | 1 | 1 |
| B | 2 | 1 |
| C | 6 | 1 |
| D | 3 | 1 |
| E | 4 | 3 |
| F | 5 | 3 |
low 值的计算依赖于回边能到达的最浅节点。例如：
- E 的 low 值为 3，因为通过回边到达 D（depth=3）
- B 的 low 值为 1，因为通过回边到达 A（depth=1）
✅ 判断关节点
以 (D, E) 为例：
- low[E] = 3 ≥ depth[D] = 3 ✅
- D 不是根节点 ✅
=> D 是关节点
类似地，我们还可以判断出 C 和 E 也是关节点。
6. 时间复杂度分析
该算法基于 DFS，因此其时间复杂度与 DFS 相同。
- 若图使用邻接表表示，DFS 的时间复杂度为 **O(V + E)**，其中 V 是顶点数，E 是边数。
- 因此，查找所有关节点的算法时间复杂度也为 **O(V + E)**。
这是非常高效的，适合处理大规模图结构。
7. 应用场景
关节点在实际中具有重要意义：
- 网络脆弱性分析：如果一个网络中存在关节点，那么该网络存在单点故障风险。
- 社交网络分析：用于识别连接不同群体的关键人物。
- 交通网络优化：识别关键枢纽节点，防止因某节点失效导致整体瘫痪。
- 最大流问题：在 max-flow min-cut 定理中，关节点常用于确定关键断点。
8. 总结
本文介绍了一个基于 DFS 的经典算法，用于识别图中的所有关节点。我们通过一个具体图示演示了算法的执行过程，并分析了其时间复杂度。
理解关节点的概念及其查找方法，有助于我们在图结构分析、网络设计、系统容错等方面做出更稳健的决策。