基于深度优先搜索的无向图割点、双连通分量及Low值求解
2026-9-26
基于深度优先搜索的无向图割点与双连通分量求解
前置约定
- 搜索源点：顶点S
- 邻居访问规则：同一节点的可访问邻居按字母升序依次访问
- 核心判定逻辑：
- 根节点为割点的充要条件：DFS树中根节点存在至少2个子节点
- 非根节点u为割点的充要条件：存在子节点v，满足
Low[v] ≥ Dfn[u]（Dfn为节点的DFS访问时间戳，Low[v]为v通过非父子回边能到达的最早访问节点的时间戳） - 双连通分量提取规则：DFS过程中遇到
Low[v] ≥ Dfn[u]时，弹出边栈中所有u到v之间的边，构成一个双连通分量
Low[v]值变化过程（按DFS访问顺序）
| 步骤 | 操作 | Dfn赋值 | Low值更新结果 |
|---|---|---|---|
| 1 | 首次访问顶点S | Dfn[S] = 1 | Low[S] = 1 |
| 2 | 首次访问顶点A（父节点为S） | Dfn[A] = 2 | Low[A] = 2 |
| 3 | 首次访问顶点B（父节点为A） | Dfn[B] =3 | Low[B] =3；发现回边B-S，更新为min(3, Dfn[S]=1) = 1 |
| 4 | 首次访问顶点D（父节点为B） | Dfn[D] =4 | Low[D] =4 |
| 5 | 首次访问顶点E（父节点为D） | Dfn[E] =5 | Low[E] =5 |
| 6 | 首次访问顶点C（父节点为E） | Dfn[C] =6 | Low[C] =6；发现回边C-A，更新为min(6, Dfn[A]=2) = 2 |
| 7 | 回溯到E | 无 | Low[E] = min(5, Low[C]=2) =2 |
| 8 | 回溯到D | 无 | Low[D] = min(4, Low[E]=2) =2 |
| 9 | 回溯到B | 无 | Low[B] = min(1, Low[D]=2) =1 |
| 10 | 回溯到A | 无 | Low[A] = min(2, Low[B]=1) =1 |
| 11 | 回溯到S | 无 | Low[S] = min(1, Low[A]=1) =1 |
最终求解结果
1. 所有割点
无符合条件的割点：
- 根节点S的DFS树仅存在1个子节点A，不符合割点判定条件
- 其余非根节点均不存在满足
Low[v] ≥ Dfn[u]的子节点，不符合割点判定条件
2. 所有双连通分量
整个无向图为一个双连通分量，包含边：S-A、S-B、A-B、A-C、B-D、D-E、C-E
内容的提问来源于stack exchange，提问作者Jane_IDK
相关产品推荐
相关产品推荐
