在图论中，割点（Articulation Point）和割边（Bridge）是描述网络脆弱性的核心概念。割点是指删除后会增加连通分量数量的顶点，割边是指删除后会增加连通分量数量的边。识别这些关键节点和边对于网络可靠性分析、电力系统故障诊断和社交网络影响力评估具有重要意义。本文将用Java实现Tarjan算法，在O(V+E)时间内高效求解无向图的割点与割边。
核心概念与定理
割点定义：在无向连通图G=(V,E)中，顶点v是割点，当且仅当删除v及其关联边后，图的连通分量数增加。
割边定义：边(u,v)是割边（桥），当且仅当删除该边后，图的连通分量数增加。
DFS树关键观察：在无向图的DFS树中，非树边只可能是回边（指向祖先），不可能是横叉边。利用这一性质，Tarjan算法通过dfn（发现时间）和low（最小可达发现时间）两个数组来识别割点和割边。
Tarjan算法原理
dfn[u]：顶点u在DFS中的发现次序（时间戳）
low[u]：从u出发通过树边和最多一条回边能到达的最小dfn值
割点判定条件：
– 根节点：若DFS树中根节点有≥2个子树，则根是割点
– 非根节点u：若存在子节点v满足low[v] ≥ dfn[u]，则u是割点
割边判定条件：
– 边(u,v)是割边，当且仅当low[v] > dfn[u]（v是u在DFS树中的子节点）
Java完整实现
import java.util.*;
/**
* Tarjan算法：求解无向图的割点与割边
* 时间复杂度: O(V + E)
* 空间复杂度: O(V + E)
*/
public class TarjanCutPointsAndBridges {
static class Edge {
int to;
int id; // 边的唯一编号，用于区分重边
Edge(int to, int id) {
this.to = to;
this.id = id;
}
}
private int n; // 顶点数
private List<Edge>[] graph; // 邻接表
private int[] dfn; // 发现时间戳
private int[] low; // 最小可达发现时间
private boolean[] isCutPoint; // 标记割点
private boolean[] isBridge; // 标记割边（按边编号）
private int timestamp; // 时间戳计数器
private int rootChildCount; // DFS树根的子树数量
private int root; // 当前DFS树根
@SuppressWarnings("unchecked")
public TarjanCutPointsAndBridges(int n) {
this.n = n;
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
dfn = new int[n];
low = new int[n];
isCutPoint = new boolean[n];
Arrays.fill(dfn, -1); // -1表示未访问
}
/**
* 添加无向边
* @param u 顶点u
* @param v 顶点v
* @param edgeId 边的唯一编号
*/
public void addEdge(int u, int v, int edgeId) {
graph[u].add(new Edge(v, edgeId));
graph[v].add(new Edge(u, edgeId));
}
/**
* 执行Tarjan算法
*/
public void execute() {
timestamp = 0;
int edgeCount = 0;
// 统计边数用于初始化isBridge
for (int i = 0; i < n; i++) {
edgeCount += graph[i].size();
}
isBridge = new boolean[edgeCount / 2]; // 无向图边数要除以2
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
root = i;
rootChildCount = 0;
tarjan(i, -1);
// 根节点割点判定：子树数量>=2
isCutPoint[root] = (rootChildCount >= 2);
}
}
}
/**
* Tarjan DFS核心
* @param u 当前顶点
* @param parentEdge 来自父节点的边编号（避免直接走回父节点）
*/
private void tarjan(int u, int parentEdge) {
dfn[u] = low[u] = ++timestamp;
for (Edge e : graph[u]) {
int v = e.to;
if (dfn[v] == -1) {
// v未访问，(u,v)是树边
if (u == root) {
rootChildCount++; // 统计根的子树数量
}
tarjan(v, e.id);
// 回溯时更新low[u]
low[u] = Math.min(low[u], low[v]);
// 割边判定：low[v] > dfn[u]
if (low[v] > dfn[u]) {
isBridge[e.id] = true;
}
// 割点判定（非根节点）：low[v] >= dfn[u]
if (u != root && low[v] >= dfn[u]) {
isCutPoint[u] = true;
}
} else if (e.id != parentEdge) {
// v已访问且不是父边，(u,v)是回边
low[u] = Math.min(low[u], dfn[v]);
}
}
}
/**
* 获取所有割点
*/
public List<Integer> getCutPoints() {
List<Integer> cutPoints = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (isCutPoint[i]) {
cutPoints.add(i);
}
}
return cutPoints;
}
/**
* 获取所有割边
*/
public List<int[]> getBridges() {
List<int[]> bridges = new ArrayList<>();
// 需要重新遍历图来找到割边对应的顶点对
boolean[] visited = new boolean[isBridge.length];
for (int u = 0; u < n; u++) {
for (Edge e : graph[u]) {
if (isBridge[e.id] && !visited[e.id]) {
visited[e.id] = true;
bridges.add(new int[]{u, e.to});
}
}
}
return bridges;
}
/**
* 打印结果
*/
public void printResults() {
System.out.println("=== Tarjan算法分析结果 ===");
System.out.println("割点: " + getCutPoints());
List<int[]> bridges = getBridges();
System.out.print("割边: ");
for (int[] bridge : bridges) {
System.out.print("(" + bridge[0] + "-" + bridge[1] + ") ");
}
System.out.println();
}
/**
* 网络可靠性分析示例
* 模拟通信网络拓扑，识别关键节点和脆弱链路
*/
public static void networkDemo() {
// 6个通信节点
int n = 6;
TarjanCutPointsAndBridges tarjan = new TarjanCutPointsAndBridges(n);
// 添加边（带唯一编号）
tarjan.addEdge(0, 1, 0);
tarjan.addEdge(1, 2, 1);
tarjan.addEdge(2, 3, 2);
tarjan.addEdge(3, 4, 3);
tarjan.addEdge(4, 5, 4); // 这是一条链上的边
tarjan.addEdge(1, 3, 5); // 形成环
tarjan.addEdge(0, 2, 6); // 另一条回边
tarjan.execute();
tarjan.printResults();
// 分析：在这个图中，顶点4和5是链的末端
// 边(4,5)应该是割边，因为5只通过4连接
System.out.println("\n网络可靠性建议:");
System.out.println("- 割点是网络中的单点故障，应增加冗余链路");
System.out.println("- 割边是瓶颈链路，应考虑升级带宽或增加备份路径");
}
/**
* 更复杂的示例：识别社交网络中的关键人物
*/
public static void socialNetworkDemo() {
int n = 7;
TarjanCutPointsAndBridges tarjan = new TarjanCutPointsAndBridges(n);
// 构建社交网络（无向图）
// 0-中心人物，连接多个群体
tarjan.addEdge(0, 1, 0);
tarjan.addEdge(0, 2, 1);
tarjan.addEdge(0, 3, 2);
tarjan.addEdge(1, 2, 3); // 群体1内部连接
tarjan.addEdge(3, 4, 4); // 连接到群体2
tarjan.addEdge(3, 5, 5);
tarjan.addEdge(4, 5, 6); // 群体2内部连接
tarjan.addEdge(3, 6, 7); // 连接到群体3
tarjan.execute();
System.out.println("=== 社交网络关键节点分析 ===");
List<Integer> cutPoints = tarjan.getCutPoints();
System.out.println("关键人物（割点）: " + cutPoints);
for (int cp : cutPoints) {
System.out.println(" 人物" + cp + " 是信息传递的关键节点");
}
}
public static void main(String[] args) {
networkDemo();
System.out.println();
socialNetworkDemo();
}
}
算法正确性证明要点
割点判定正确性：
– 对于非根节点u，若子节点v满足low[v] ≥ dfn[u]，说明v及其子树中的顶点无法通过回边到达u的祖先。因此删除u后，v的子树将与u的祖先分离，连通分量增加。
– 对于根节点，若有≥2棵子树，由于无向图中不同子树之间不存在横叉边（只能通过根相连），删除根后各子树互不相连。
割边判定正确性：
– low[v] > dfn[u]意味着v的子树中不存在指向u或u祖先的回边。因此边(u,v)是连接两部分的唯一路径，删除后必然分离。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(V + E) | 每条边和每个顶点仅访问一次 |
| 空间 | O(V + E) | 邻接表 + 几个辅助数组 |
扩展应用
- 双连通分量：删除割点后，图分裂成的每个连通块称为双连通分量
- 边双连通分量：删除割边后，剩余的每个连通块
- 2-顶点连通图：无割点的图，任意两点间存在两条顶点不相交路径
- 2-边连通图：无割边的图，任意两点间存在两条边不相交路径
