Articulation Point（割点）算法详解
割点（Articulation Point） 是图论中的一个非常经典的问题：
在无向图中，如果删除某个顶点会导致图不连通，则该顶点就是一个割点。
本篇文章将基于 TheAlgorithms/Go 实现的版本，对代码进行完整中文解读，并详细解释其中的 DFS（深度优先搜索）与“时间戳”逻辑，从而帮助读者彻底理解割点的判断方式。
一、Articulation Point（割点）是什么？
我们在图中找一个点，如果删掉这个点（以及与它相连的边），图会被拆成多个不连通部分，那么这个点就是“割点”。
例如：
A - B - C - D|E顶点 B 是割点，因为删除 B 后，E 会与其他点断开。
割点广泛用于：
- 网络可靠性分析
- 社交网络关键人物分析
- 通信链路的冗余分析
- 强连通性算法
- 拓扑结构弱点定位
二、算法基础：DFS + 时间戳（Tarjan 思想）
算法核心思想：
- 对每个节点 DFS 编号，得到 discovery time
- 同时计算每个节点能回退到的最早时间戳 low-link（earliest discovery）
- 如果满足：
low[child] >= disc[parent]
则 parent 是一个割点
代表：子节点无法通过回边访问到父节点之前的节点 → 割裂发生
特殊规则：
- 根节点如果有 两个及以上的子树 才是割点
三、代码中文翻译（逐行解释版）
下面是你给出的代码的中文翻译版＋中文注释。
✨ 代码中文翻译与注释
// Package graph 提供图结构分析相关的算法。
package graph
import "github.com/TheAlgorithms/Go/math/min"
// apHelper 用于在搜索割点过程中存储辅助数据。
type apHelper struct {
isAP []bool // 标记每个顶点是否为割点
visited []bool // DFS 是否访问过
childCount []int // 每个顶点的子节点数（仅 DFS 树意义）
discoveryTime []int // DFS 遍历时节点的发现时间戳
earliestDiscovery []int // 能回退到的最早时间（low-link 值）
}
// ArticulationPoint 用于寻找图中的割点。
// 返回一个布尔切片，表示每个顶点是否是割点。
// 时间复杂度：O(|V| + |E|)
// 空间复杂度：O(|V|)
func ArticulationPoint(graph *Graph) []bool {
// time 用于记录 DFS 访问时间戳
time := 0
// apHelper 结构初始化
apHelperInstance := &apHelper{
isAP: make([]bool, graph.vertices),
visited: make([]bool, graph.vertices),
childCount: make([]int, graph.vertices),
discoveryTime: make([]int, graph.vertices),
earliestDiscovery: make([]int, graph.vertices),
}
// 从根节点 0 开始 DFS
articulationPointHelper(apHelperInstance, 0, -1, &time, graph)
// 根节点如果只有一个孩子，则不能视为割点
if apHelperInstance.childCount[0] == 1 {
apHelperInstance.isAP[0] = false
}
return apHelperInstance.isAP
}
// articulationPointHelper 通过 DFS 遍历图并标记割点。
// 更新 childCount、discoveryTime 和 earliestDiscovery。
func articulationPointHelper(
apHelperInstance *apHelper,
vertex int,
parent int,
time *int,
graph *Graph,
) {
apHelperInstance.visited[vertex] = true
// 设置发现时间和最早可回退时间
apHelperInstance.discoveryTime[vertex] = *time
apHelperInstance.earliestDiscovery[vertex] = *time
*time++
for nextVertex := range graph.edges[vertex] {
// 跳过父节点
if nextVertex == parent {
continue
}
if apHelperInstance.visited[nextVertex] {
// 遇到回边，更新 low-link
apHelperInstance.earliestDiscovery[vertex] = min.Int(
apHelperInstance.earliestDiscovery[vertex],
apHelperInstance.discoveryTime[nextVertex],
)
continue
}
// 作为 DFS 子节点计数
apHelperInstance.childCount[vertex]++
articulationPointHelper(apHelperInstance, nextVertex, vertex, time, graph)
// DFS 完成后更新 earliestDiscovery
apHelperInstance.earliestDiscovery[vertex] = min.Int(
apHelperInstance.earliestDiscovery[vertex],
apHelperInstance.earliestDiscovery[nextVertex],
)
// 满足割点条件
if apHelperInstance.earliestDiscovery[nextVertex] >= apHelperInstance.discoveryTime[vertex] {
apHelperInstance.isAP[vertex] = true
}
}
}四、算法关键逻辑解析
1. discoveryTime（发现时间）
DFS 每访问一个节点，会赋予一个递增时间戳。
例如：
0 → 1 → 3 → 4 → 2发现时间可能是：
disc = [0, 1, 4, 2, 3]2. earliestDiscovery（low-link 值）
表示该节点通过“回边”能跳到的最早祖先。
计算方式：
earliest[v] = min(earliest[v], discovery[u])或在 DFS 回溯时更新：
earliest[parent] = min(earliest[parent], earliest[child])3. 割点判定条件
非根节点
如果：
low[child] >= disc[parent]则 parent 是割点。
因为 child 无法回到 parent 之前 → 删除 parent 会断链。
4. 根节点单独判断
根节点必须有 两个及以上子树 才是割点。
五、图示理解（低值回退）
节点 A → B → C
如果 C 有一条边连回 A，则 low[C] 会是 disc[A]，因此 B 不是割点
A
| \
| C
|
B六、总结
| 名称 | 含义 |
|---|---|
| discoveryTime | DFS 第几次访问到 |
| earliestDiscovery（low-link） | 能回退到的最早祖先 |
| childCount | 根节点割点判定专用 |
| isAP | 是否为割点 |
算法性能：
- 时间复杂度：O(V + E)
- 空间复杂度：O(V)
- 使用 DFS + Tarjan 思想，是最优解法