割点与桥
📌 定义
割点（Cut Vertex）：删除该点及其相连的边后，图的连通分量数增加。
桥（Bridge/Cut Edge）：删除该边后，图的连通分量数增加。
图示例:
0---1---2
| | |
3---4 5
割点: 1, 2
桥: (1,2), (2,5)
核心思路
- DFS遍历：使用深度优先搜索
- 时间戳：记录节点的访问时间
- Low值：能回溯到的最早时间戳
- 判断条件：根据dfn和low的关系判断
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V+E) | 一次DFS |
| 空间复杂度 | O(V) | 递归栈 |
Go 代码
Go 实现
package main
func FindArticulationPoints(graph [][]int, n int) []int {
dfn := make([]int, n)
low := make([]int, n)
parent := make([]int, n)
isArticulation := make([]bool, n)
time := 0
for i := range dfn {
dfn[i] = -1
low[i] = -1
parent[i] = -1
}
var dfs func(int)
dfs = func(u int) {
children := 0
dfn[u] = time
low[u] = time
time++
for _, v := range graph[u] {
if dfn[v] == -1 {
children++
parent[v] = u
dfs(v)
if low[v] < low[u] {
low[u] = low[v]
}
if parent[u] == -1 && children > 1 {
isArticulation[u] = true
}
if parent[u] != -1 && low[v] >= dfn[u] {
isArticulation[u] = true
}
} else if v != parent[u] {
if dfn[v] < low[u] {
low[u] = dfn[v]
}
}
}
}
for i := 0; i < n; i++ {
if dfn[i] == -1 {
dfs(i)
}
}
result := []int{}
for i := 0; i < n; i++ {
if isArticulation[i] {
result = append(result, i)
}
}
return result
}
func FindBridges(graph [][]int, n int) [][2]int {
dfn := make([]int, n)
low := make([]int, n)
parent := make([]int, n)
bridges := [][2]int{}
time := 0
for i := range dfn {
dfn[i] = -1
low[i] = -1
parent[i] = -1
}
var dfs func(int)
dfs = func(u int) {
dfn[u] = time
low[u] = time
time++
for _, v := range graph[u] {
if dfn[v] == -1 {
parent[v] = u
dfs(v)
if low[v] < low[u] {
low[u] = low[v]
}
if low[v] > dfn[u] {
bridges = append(bridges, [2]int{u, v})
}
} else if v != parent[u] {
if dfn[v] < low[u] {
low[u] = dfn[v]
}
}
}
}
for i := 0; i < n; i++ {
if dfn[i] == -1 {
dfs(i)
}
}
return bridges
}思路展开
割点判断条件
- 根节点：有两个或以上的子树
- 非根节点：存在子节点v，使得
low[v] >= dfn[u]
桥判断条件
边(u,v)是桥，当且仅当：low[v] > dfn[u]
执行示例
图:
0---1---2
| | |
3---4 5
DFS从节点0开始:
访问0: dfn[0]=0, low[0]=0
访问1: dfn[1]=1, low[1]=1
访问2: dfn[2]=2, low[2]=2
访问5: dfn[5]=3, low[5]=3
回溯: low[2]=min(2,3)=2
回溯: low[1]=min(1,2)=1
访问4: dfn[4]=4, low[4]=4
访问3: dfn[3]=5, low[3]=5
回边到0: low[3]=min(5,0)=0
回溯: low[4]=min(4,0)=0
回溯: low[1]=min(1,0)=0
回溯: low[0]=min(0,0)=0
判断割点:
- 节点1: low[2]=2 >= dfn[1]=1 ✓ (割点)
- 节点2: low[5]=3 >= dfn[2]=2 ✓ (割点)
判断桥:
- 边(1,2): low[2]=2 > dfn[1]=1 ✓ (桥)
- 边(2,5): low[5]=3 > dfn[2]=2 ✓ (桥)
经典题目
💡 优缺点
优点
- ✅ 时间复杂度O(V+E)
- ✅ 一次DFS完成
- ✅ 空间效率高
缺点
- ❌ 理解较难
- ❌ 实现细节多