问题引入
在图论中，连通性分析是网络可靠性评估的核心。割点是删除后会增加连通分量数量的顶点，割边（桥）是删除后会增加连通分量数量的边。双连通分量则是没有割点的极大子图，分为点双连通分量（任意两点间存在不经过其他点的路径）和边双连通分量（任意两点间存在不共享边的路径）。本文用Java实现Tarjan算法，基于DFS树和lowlink值，在O(V+E)时间内同时求出割点、割边和双连通分量。
算法原理
DFS树与lowlink值
对无向图进行DFS时，边分为树边（连接父节点）和回边（连接到祖先）。每个节点u维护两个值：
– dfn[u]：DFS遍历序号（发现时间）
– low[u]：从u出发通过树边和至多一条回边能到达的最小dfn值
low[u]的计算方式为：
low[u] = min(dfn[u], low[v] (v是u的子节点), dfn[w] (w通过回边到达的祖先))
割点判定
对于DFS树的根节点，若它有两个或以上子树，则它是割点。对于非根节点u，若存在子节点v满足low[v] >= dfn[u]，则u是割点。这意味着v的子树无法通过回边绕过u到达u的祖先。
割边判定
对于树边(u, v)（u是v的父节点），若low[v] > dfn[u]，则该边是割边。严格大于表示v的子树没有任何回边连接到u或其祖先。
边双连通分量
将所有割边删除后，剩余的每个连通块即为一个边双连通分量。可通过一次DFS，不经过割边遍历到的所有节点属于同一个边双连通分量。
完整Java实现
package algorithm.biconnected;
import java.util.*;
/**
* Tarjan算法：割点、割边与双连通分量
* 时间复杂度O(V+E)，空间复杂度O(V+E)
*/
public class TarjanBiconnected {
private final int n;
private final List<List<int[]>> graph; // [邻居, 边编号]
private int[] dfn;
private int[] low;
private boolean[] isCutVertex;
private boolean[] isBridge;
private int timestamp;
private final List<List<Integer>> edgeBCCs; // 边双连通分量
private final List<int[]> bridges; // 割边列表
public TarjanBiconnected(int n) {
this.n = n;
this.graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
this.bridges = new ArrayList<>();
this.edgeBCCs = new ArrayList<>();
}
/**
* 添加无向边
* @param u 端点1
* @param v 端点2
* @param edgeId 边编号（用于区分重边）
*/
public void addEdge(int u, int v, int edgeId) {
graph.get(u).add(new int[]{v, edgeId});
graph.get(v).add(new int[]{u, edgeId});
}
/**
* 执行Tarjan算法
*/
public void run() {
dfn = new int[n];
low = new int[n];
isCutVertex = new boolean[n];
isBridge = new boolean[n + n]; // 边编号作为索引
timestamp = 0;
Arrays.fill(dfn, -1);
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
tarjan(i, -1);
}
}
}
private void tarjan(int u, int parentEdge) {
dfn[u] = low[u] = ++timestamp;
int childCount = 0;
for (int[] edge : graph.get(u)) {
int v = edge[0];
int eid = edge[1];
if (eid == parentEdge) continue; // 跳过来时的边
if (dfn[v] == -1) {
// 树边，继续DFS
childCount++;
tarjan(v, eid);
low[u] = Math.min(low[u], low[v]);
// 割边判定
if (low[v] > dfn[u]) {
isBridge[eid] = true;
bridges.add(new int[]{u, v});
}
// 割点判定（非根节点）
if (parentEdge != -1 && low[v] >= dfn[u]) {
isCutVertex[u] = true;
}
} else {
// 回边，更新low值
low[u] = Math.min(low[u], dfn[v]);
}
}
// 根节点割点判定
if (parentEdge == -1 && childCount >= 2) {
isCutVertex[u] = true;
}
}
/**
* 计算边双连通分量（删除所有桥后剩余的连通块）
*/
public void computeEdgeBCCs() {
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
List<Integer> bcc = new ArrayList<>();
dfsBCC(i, visited, bcc);
if (!bcc.isEmpty()) {
edgeBCCs.add(bcc);
}
}
}
}
private void dfsBCC(int u, boolean[] visited, List<Integer> bcc) {
visited[u] = true;
bcc.add(u);
for (int[] edge : graph.get(u)) {
int v = edge[0];
int eid = edge[1];
if (isBridge[eid]) continue; // 不经过桥
if (!visited[v]) {
dfsBCC(v, visited, bcc);
}
}
}
public boolean[] getCutVertices() {
return isCutVertex;
}
public List<int[]> getBridges() {
return bridges;
}
public List<List<Integer>> getEdgeBCCs() {
return edgeBCCs;
}
public static void main(String[] args) {
// 示例图：
// 0 -- 1 -- 2
// | | |
// 3 -- 4 -- 5
// 边(1,4)和(2,5)是桥（假设额外分支）
TarjanBiconnected tarjan = new TarjanBiconnected(6);
tarjan.addEdge(0, 1, 0);
tarjan.addEdge(1, 2, 1);
tarjan.addEdge(0, 3, 2);
tarjan.addEdge(3, 4, 3);
tarjan.addEdge(1, 4, 4);
tarjan.addEdge(4, 5, 5);
tarjan.addEdge(2, 5, 6);
tarjan.run();
tarjan.computeEdgeBCCs();
System.out.println("=== 割点 ===");
boolean[] cut = tarjan.getCutVertices();
for (int i = 0; i < cut.length; i++) {
if (cut[i]) System.out.println("顶点 " + i);
}
System.out.println("\n=== 割边（桥）===");
for (int[] bridge : tarjan.getBridges()) {
System.out.println(bridge[0] + " -- " + bridge[1]);
}
System.out.println("\n=== 边双连通分量 ===");
List<List<Integer>> bccs = tarjan.getEdgeBCCs();
for (int i = 0; i < bccs.size(); i++) {
System.out.println("分量 " + (i + 1) + ": " + bccs.get(i));
}
// 示例2：带桥结构
System.out.println("\n=== 示例2：带桥的图 ===");
TarjanBiconnected g2 = new TarjanBiconnected(7);
g2.addEdge(0, 1, 0);
g2.addEdge(1, 2, 1);
g2.addEdge(2, 0, 2); // 三角形
g2.addEdge(1, 3, 3); // 桥
g2.addEdge(3, 4, 4);
g2.addEdge(4, 5, 5);
g2.addEdge(5, 3, 6); // 另一个三角形
g2.addEdge(4, 6, 7); // 桥
g2.run();
g2.computeEdgeBCCs();
System.out.println("割点:");
boolean[] cut2 = g2.getCutVertices();
for (int i = 0; i < cut2.length; i++) if (cut2[i]) System.out.print(i + " ");
System.out.println("\n割边:");
for (int[] b : g2.getBridges()) System.out.println(b[0] + " -- " + b[1]);
System.out.println("边双连通分量:");
for (List<Integer> bcc : g2.getEdgeBCCs()) System.out.println(bcc);
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(V + E) | 每个节点和边仅访问一次 |
| 空间 | O(V + E) | 邻接表 + 辅助数组 |
Tarjan算法是线性时间算法，效率极高。对于10^5节点、10^6边规模的图，Java实现可在毫秒级完成计算。
关键技巧总结
low[v] > dfn[u]中的严格大于号判断割边，等于号判断割点，区别需注意- 无向图中需跳过父边（通过边编号区分），但不能简单跳过父节点（因可能有重边）
- 根节点割点判定条件为子树数量≥2，与非根节点的
low[v] >= dfn[u]不同 - 边双连通分量的提取只需在DFS时避开所有桥即可，无需额外复杂逻辑
- 点双连通分量（点双）需要借助栈在DFS过程中维护路径，实现比边双更复杂
