引言
在无向图中，割点（Articulation Point）是指删除后会增加连通分量数量的顶点，割边（Bridge）是指删除后会增加连通分量数量的边。它们在分析网络脆弱性、设计容错系统以及通信网络优化中具有重要价值。本文使用Java实现Tarjan算法高效求解无向图的割点与割边，并应用于网络拓扑的脆弱性分析。
核心概念
割点（Articulation Point）：在无向连通图中，如果删除顶点 v 及其所有关联边后，图的连通分量数量增加，则称 v 为割点。
割边（Bridge）：在无向连通图中，如果删除边 (u, v) 后，图的连通分量数量增加，则称该边为割边。
low值：顶点 v 的 low 值定义为从 v 出发通过树边至多一条回边能够到达的最小发现时间戳（dfn）。
Tarjan算法原理
Tarjan算法通过一次深度优先搜索（DFS）即可找出所有割点和割边，核心判断条件：
- 割点判定：
- 根节点：如果有两个或以上的子树，则是割点
-
非根节点 u：如果存在子节点 v 满足
low[v] >= dfn[u]，则 u 是割点 -
割边判定：
- 边 (u, v) 是割边当且仅当
low[v] > dfn[u]（v 是 u 的子节点）
Java实现
import java.util.*;
/**
* Tarjan算法：求解无向图的割点与割边
*/
public class TarjanAlgorithm {
private int n; // 顶点数量
private List<Integer>[] graph; // 邻接表
private int[] dfn; // 发现时间戳
private int[] low; // 能到达的最小时间戳
private boolean[] visited;
private boolean[] isArticulation; // 标记割点
private List<int[]> bridges; // 存储割边
private int timestamp;
@SuppressWarnings("unchecked")
public TarjanAlgorithm(int n) {
this.n = n;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
this.dfn = new int[n];
this.low = new int[n];
this.visited = new boolean[n];
this.isArticulation = new boolean[n];
this.bridges = new ArrayList<>();
this.timestamp = 0;
}
public void addEdge(int u, int v) {
graph[u].add(v);
graph[v].add(u);
}
/**
* 执行Tarjan算法，找出所有割点和割边
*/
public void execute() {
for (int i = 0; i < n; i++) {
if (!visited[i]) {
tarjanDFS(i, -1);
}
}
}
/**
* Tarjan DFS核心递归
* @param u 当前顶点
* @param parent 父顶点
*/
private void tarjanDFS(int u, int parent) {
visited[u] = true;
dfn[u] = low[u] = ++timestamp;
int childCount = 0; // 记录u在DFS树中的子节点数量（用于根节点判断）
for (int v : graph[u]) {
if (v == parent) {
// 跳过直接父节点，但注意：需要处理重边情况
continue;
}
if (!visited[v]) {
// 树边：v是u的子节点
childCount++;
tarjanDFS(v, u);
// 回溯时更新low值
low[u] = Math.min(low[u], low[v]);
// 割点判定：非根节点，且子节点v无法绕过u到达更早的祖先
if (parent != -1 && low[v] >= dfn[u]) {
isArticulation[u] = true;
}
// 割边判定：v无法绕过边(u,v)到达u或更早的祖先
if (low[v] > dfn[u]) {
bridges.add(new int[]{u, v});
}
} else {
// 回边：v已被访问且不是父节点
low[u] = Math.min(low[u], dfn[v]);
}
}
// 根节点割点判定：有两个或以上子树
if (parent == -1 && childCount >= 2) {
isArticulation[u] = true;
}
}
/**
* 获取所有割点
*/
public List<Integer> getArticulationPoints() {
List<Integer> points = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (isArticulation[i]) {
points.add(i);
}
}
return points;
}
/**
* 获取所有割边
*/
public List<int[]> getBridges() {
return bridges;
}
/**
* 重置状态，允许重新计算
*/
public void reset() {
Arrays.fill(dfn, 0);
Arrays.fill(low, 0);
Arrays.fill(visited, false);
Arrays.fill(isArticulation, false);
bridges.clear();
timestamp = 0;
}
处理重边与自环的健壮版本
/**
* 健壮版DFS：正确处理重边（多条相同顶点之间的边）
* 使用边的编号而非顶点判断父关系
*/
private List<int[]> edgeList; // 存储边 [u, v]
private List<int[]>[] edgeGraph; // edgeGraph[u] = list of [v, edgeId]
@SuppressWarnings("unchecked")
public TarjanAlgorithmRobust(int n) {
this.n = n;
this.edgeGraph = new ArrayList[n];
for (int i = 0; i < n; i++) {
edgeGraph[i] = new ArrayList<>();
}
this.dfn = new int[n];
this.low = new int[n];
this.visited = new boolean[n];
this.isArticulation = new boolean[n];
this.bridges = new ArrayList<>();
this.edgeList = new ArrayList<>();
this.timestamp = 0;
}
public void addEdgeRobust(int u, int v) {
int edgeId = edgeList.size();
edgeList.add(new int[]{u, v});
edgeGraph[u].add(new int[]{v, edgeId});
edgeGraph[v].add(new int[]{u, edgeId});
}
private void tarjanRobustDFS(int u, int parentEdgeId) {
visited[u] = true;
dfn[u] = low[u] = ++timestamp;
int childCount = 0;
for (int[] next : edgeGraph[u]) {
int v = next[0];
int edgeId = next[1];
if (edgeId == parentEdgeId) continue; // 通过边ID判断，正确处理重边
if (!visited[v]) {
childCount++;
tarjanRobustDFS(v, edgeId);
low[u] = Math.min(low[u], low[v]);
if (parentEdgeId != -1 && low[v] >= dfn[u]) {
isArticulation[u] = true;
}
if (low[v] > dfn[u]) {
bridges.add(new int[]{u, v});
}
} else {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (parentEdgeId == -1 && childCount >= 2) {
isArticulation[u] = true;
}
}
网络脆弱性分析应用
/**
* 计算删除每个割点后，各连通分量的大小
* 用于评估网络中关键节点的脆弱性影响
*/
public Map<Integer, List<Integer>> analyzeVulnerability() {
Map<Integer, List<Integer>> vulnerabilityMap = new HashMap<>();
for (int ap : getArticulationPoints()) {
// 临时移除割点ap，计算连通分量
boolean[] tempVisited = new boolean[n];
List<Integer> componentSizes = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i != ap && !tempVisited[i]) {
int size = countComponent(i, ap, tempVisited);
componentSizes.add(size);
}
}
vulnerabilityMap.put(ap, componentSizes);
}
return vulnerabilityMap;
}
private int countComponent(int start, int blocked, boolean[] tempVisited) {
tempVisited[start] = true;
int count = 1;
for (int v : graph[start]) {
if (v != blocked && !tempVisited[v]) {
count += countComponent(v, blocked, tempVisited);
}
}
return count;
}
完整测试
public static void main(String[] args) {
// 构建测试图：一个典型的包含割点和割边的图
// 0 --- 1
// | |
// 2 --- 3 --- 4
// |
// 5
TarjanAlgorithm tarjan = new TarjanAlgorithm(6);
tarjan.addEdge(0, 1);
tarjan.addEdge(0, 2);
tarjan.addEdge(1, 3);
tarjan.addEdge(2, 3);
tarjan.addEdge(3, 4);
tarjan.addEdge(3, 5);
tarjan.execute();
System.out.println("=== Tarjan算法：割点与割边分析 ===\n");
System.out.println("割点: " + tarjan.getArticulationPoints());
System.out.println("割边: " + formatBridges(tarjan.getBridges()));
System.out.println("\n脆弱性分析:");
Map<Integer, List<Integer>> vuln = tarjan.analyzeVulnerability();
for (Map.Entry<Integer, List<Integer>> entry : vuln.entrySet()) {
System.out.println(" 删除割点 " + entry.getKey() + " 后连通分量大小: " + entry.getValue());
}
}
private static String formatBridges(List<int[]> bridges) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < bridges.size(); i++) {
sb.append("(").append(bridges.get(i)[0]).append(",").append(bridges.get(i)[1]).append(")");
if (i < bridges.size() - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
复杂度分析
| 指标 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Tarjan DFS | O(V + E) | O(V) |
| 脆弱性分析 | O(V * (V + E)) | O(V) |
其中 V 为顶点数，E 为边数。Tarjan算法仅需一次DFS，效率极高。
总结
本文通过Tarjan算法实现了无向图割点与割边的高效求解，并扩展到网络脆弱性分析场景。读者可以掌握DFS树、low值、dfn值等核心概念，并将其应用于网络拓扑分析、社交网络关键节点识别等实际问题中。
