每日算法 — 使用java实现割点与割边：DFS lowlink与图连通性分析

在无向图中，割点（Articulation Point）是指删除该点后图的连通分量数增加的顶点；割边（Bridge）是指删除该边后图的连通分量数增加的边。割点和割边在网络可靠性分析、交通路网设计、社交网络关键节点识别等领域有重要应用。本文用 Java 实现基于 DFS lowlink 值的割点割边判定算法，并扩展至双连通分量的分解。

一、算法原理：DFS 树与 lowlink

对无向图执行 DFS，得到一棵 DFS 生成树。图中的边分为两类：
– 树边：DFS 遍历经过的边
– 回边：连接节点与其祖先的非树边

定义两个时间戳数组：
– dfn[u]：节点 u 的 DFS 发现时间
– low[u]：从 u 出发通过树边和至多一条回边能到达的最小 dfn 值

low[u] = min(dfn[u], min(low[v] for v is child of u), min(dfn[w] for (u,w) is back edge))

1.1 割点判定

对于 DFS 树的根节点 u：若 u 有两个或以上子树，则 u 是割点。

对于非根节点 u：若 u 存在子节点 v 满足 low[v] ≥ dfn[u]，则 u 是割点。

含义：v 及其子树无法通过回边到达 u 的祖先，因此删除 u 后 v 子树与图其余部分断开。

1.2 割边判定

树边 (u, v) 是割边当且仅当 low[v] > dfn[u]（v 是 u 的子节点）。

含义：v 及其子树无法通过回边到达 u 或其祖先，删除该边后 v 子树被分离。

二、Java 完整实现

import java.util.*;

/**
 * 割点与割边求解器
 * 核心算法：DFS + lowlink 值
 */
public class ArticulationPointBridge {

    private int n;                    // 顶点数
    private List<Integer>[] adj;      // 邻接表
    private int[] dfn;                // DFS发现时间
    private int[] low;                // 能回溯到的最小时间
    private boolean[] visited;
    private int timestamp;

    private boolean[] isArticulation; // 割点标记
    private List<int[]> bridges;      // 割边列表 [u, v]

    @SuppressWarnings("unchecked")
    public ArticulationPointBridge(int n) {
        this.n = n;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[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<>();
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }

    /**
     * DFS 求割点和割边
     * @param u 当前节点
     * @param parent 父节点（-1表示根）
     */
    private void dfs(int u, int parent) {
        visited[u] = true;
        dfn[u] = low[u] = ++timestamp;
        int childCount = 0; // 用于根节点的子树计数

        for (int v : adj[u]) {
            if (!visited[v]) {
                childCount++;
                dfs(v, u);

                // 回溯时更新 low[u]
                low[u] = Math.min(low[u], low[v]);

                // 割点判定（非根节点）
                if (parent != -1 && low[v] >= dfn[u]) {
                    isArticulation[u] = true;
                }

                // 割边判定
                if (low[v] > dfn[u]) {
                    bridges.add(new int[]{u, v});
                }

            } else if (v != parent) {
                // 回边：更新 low[u]
                // 注意：无向图中要排除父节点，但需处理重边情况
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        // 根节点的割点判定
        if (parent == -1 && childCount >= 2) {
            isArticulation[u] = true;
        }
    }

    /**
     * 处理重边情况：使用边编号而非顶点判断父节点
     */
    private void dfsWithEdgeId(int u, int edgeId) {
        visited[u] = true;
        dfn[u] = low[u] = ++timestamp;
        int childCount = 0;

        for (int[] next : adjWithEdgeId.get(u)) {
            int v = next[0];
            int eid = next[1];

            if (!visited[v]) {
                childCount++;
                dfsWithEdgeId(v, eid);
                low[u] = Math.min(low[u], low[v]);

                if (edgeId != -1 && low[v] >= dfn[u]) {
                    isArticulation[u] = true;
                }
                if (low[v] > dfn[u]) {
                    bridges.add(new int[]{u, v});
                }
            } else if (eid != edgeId) {
                // 只通过非当前边的回边更新
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (edgeId == -1 && childCount >= 2) {
            isArticulation[u] = true;
        }
    }

    private List<int[]>[] adjWithEdgeId; // [v, edgeId]
    private int edgeCounter;

    /**
     * 添加带编号的边（用于处理重边）
     */
    public void addEdgeWithId(int u, int v) {
        if (adjWithEdgeId == null) {
            adjWithEdgeId = new ArrayList[n];
            for (int i = 0; i < n; i++) adjWithEdgeId[i] = new ArrayList<>();
            edgeCounter = 0;
        }
        adjWithEdgeId[u].add(new int[]{v, edgeCounter});
        adjWithEdgeId[v].add(new int[]{u, edgeCounter});
        edgeCounter++;
    }

    /**
     * 执行割点割边计算（简单图版本）
     */
    public void solve() {
        Arrays.fill(visited, false);
        Arrays.fill(isArticulation, false);
        Arrays.fill(dfn, 0);
        Arrays.fill(low, 0);
        bridges.clear();
        timestamp = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, -1);
            }
        }
    }

    /**
     * 执行割点割边计算（支持重边版本）
     */
    public void solveWithEdgeId() {
        Arrays.fill(visited, false);
        Arrays.fill(isArticulation, false);
        Arrays.fill(dfn, 0);
        Arrays.fill(low, 0);
        bridges.clear();
        timestamp = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfsWithEdgeId(i, -1);
            }
        }
    }

    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 new ArrayList<>(bridges);
    }

    /**
     * 求边双连通分量（删除割边后的连通块）
     */
    public List<List<Integer>> getEdgeBiconnectedComponents() {
        // 临时移除割边，然后做连通分量标记
        boolean[][] isBridge = new boolean[n][n];
        for (int[] b : bridges) {
            isBridge[b[0]][b[1]] = isBridge[b[1]][b[0]] = true;
        }

        List<List<Integer>> components = new ArrayList<>();
        boolean[] compVisited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (compVisited[i]) continue;
            List<Integer> comp = new ArrayList<>();
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            compVisited[i] = true;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                comp.add(u);
                for (int v : adj[u]) {
                    if (!compVisited[v] && !isBridge[u][v]) {
                        compVisited[v] = true;
                        queue.add(v);
                    }
                }
            }
            if (!comp.isEmpty()) components.add(comp);
        }

        return components;
    }

    /**
     * 求点双连通分量（基于割点的块分解）
     * 使用栈记录 DFS 路径上的边
     */
    public List<List<int[]>> getVertexBiconnectedComponents() {
        List<List<int[]>> components = new ArrayList<>();
        Stack<int[]> edgeStack = new Stack<>();
        boolean[] vVisited = new boolean[n];
        int[] vDfn = new int[n];
        int[] vLow = new int[n];
        int[] vTime = {0};

        for (int i = 0; i < n; i++) {
            if (!vVisited[i]) {
                findVertexBCC(i, -1, vVisited, vDfn, vLow, vTime, edgeStack, components);
                // 弹出剩余边
                if (!edgeStack.isEmpty()) {
                    List<int[]> comp = new ArrayList<>();
                    while (!edgeStack.isEmpty()) comp.add(edgeStack.pop());
                    components.add(comp);
                }
            }
        }

        return components;
    }

    private void findVertexBCC(int u, int parent, boolean[] vis, int[] d, int[] l, 
                                int[] t, Stack<int[]> stack, List<List<int[]>> comps) {
        vis[u] = true;
        d[u] = l[u] = ++t[0];

        for (int v : adj[u]) {
            if (!vis[v]) {
                stack.push(new int[]{u, v});
                findVertexBCC(v, u, vis, d, l, t, stack, comps);
                l[u] = Math.min(l[u], l[v]);

                if (l[v] >= d[u]) {
                    // 找到一个点双连通分量
                    List<int[]> comp = new ArrayList<>();
                    while (!stack.isEmpty()) {
                        int[] edge = stack.pop();
                        comp.add(edge);
                        if ((edge[0] == u && edge[1] == v) || (edge[0] == v && edge[1] == u)) {
                            break;
                        }
                    }
                    comps.add(comp);
                }
            } else if (v != parent && d[v] < d[u]) {
                // 回边，且只向祖先连边避免重复
                stack.push(new int[]{u, v});
                l[u] = Math.min(l[u], d[v]);
            }
        }
    }

    public static void main(String[] args) {
        // 测试图1：经典示例
        //     0
        //    / \
        //   1---2
        //   |   |
        //   3---4
        System.out.println("=== 测试图1：基础连通图 ===");
        ArticulationPointBridge solver1 = new ArticulationPointBridge(5);
        solver1.addEdge(0, 1);
        solver1.addEdge(0, 2);
        solver1.addEdge(1, 2);
        solver1.addEdge(1, 3);
        solver1.addEdge(2, 4);
        solver1.addEdge(3, 4);
        solver1.solve();

        System.out.println("割点: " + solver1.getArticulationPoints()); // []
        System.out.println("割边: " + formatEdges(solver1.getBridges())); // []

        // 测试图2：含割点和割边
        //     0
        //    / \
        //   1   2
        //   |   |
        //   3   4---5
        System.out.println("\n=== 测试图2：含割点和割边 ===");
        ArticulationPointBridge solver2 = new ArticulationPointBridge(6);
        solver2.addEdge(0, 1);
        solver2.addEdge(0, 2);
        solver2.addEdge(1, 3);
        solver2.addEdge(2, 4);
        solver2.addEdge(4, 5);
        solver2.solve();

        System.out.println("割点: " + solver2.getArticulationPoints()); // [0, 2, 4]
        System.out.println("割边: " + formatEdges(solver2.getBridges())); // [(0,1), (1,3), (2,4), (4,5)]

        // 测试图3：链状图
        System.out.println("\n=== 测试图3：链状图 ===");
        ArticulationPointBridge solver3 = new ArticulationPointBridge(4);
        solver3.addEdge(0, 1);
        solver3.addEdge(1, 2);
        solver3.addEdge(2, 3);
        solver3.solve();

        System.out.println("割点: " + solver3.getArticulationPoints()); // [1, 2]
        System.out.println("割边: " + formatEdges(solver3.getBridges())); // 所有边

        // 测试图4：含重边
        System.out.println("\n=== 测试图4：含重边（需用 edgeId 版本） ===");
        ArticulationPointBridge solver4 = new ArticulationPointBridge(3);
        solver4.addEdgeWithId(0, 1);
        solver4.addEdgeWithId(0, 1); // 重边
        solver4.addEdgeWithId(1, 2);
        solver4.solveWithEdgeId();

        System.out.println("割点: " + solver4.getArticulationPoints()); // [1]（0-1间的重边使0-1不再是割边，但1仍是割点）
        System.out.println("割边: " + formatEdges(solver4.getBridges())); // [(1,2)]

        // 边双连通分量测试
        System.out.println("\n=== 边双连通分量测试（测试图2） ===");
        List<List<Integer>> ebcc = solver2.getEdgeBiconnectedComponents();
        for (int i = 0; i < ebcc.size(); i++) {
            System.out.println("分量 " + (i+1) + ": " + ebcc.get(i));
        }
    }

    private static String formatEdges(List<int[]> edges) {
        StringBuilder sb = new StringBuilder("[");
        for (int[] e : edges) {
            sb.append("(").append(e[0]).append(",").append(e[1]).append(") ");
        }
        if (!edges.isEmpty()) sb.setLength(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }
}

三、复杂度分析

所有操作均为线性时间，这是 Tarjan 系列算法的标志性特征。

四、易错点与注意事项

1. 根节点的特殊处理：根节点是割点的判定条件与普通节点不同，必须有两个以上子树
2. 重边的影响：简单版本中通过 v != parent 判断回边，在有重边时会误判。应使用边编号区分
3. 自环的处理：自环不影响割点割边判定，DFS 中可忽略
4. low 值更新方向：只能通过回边向祖先更新，不能向子孙更新（即只接受 dfn[v] < dfn[u] 的更新）

五、实际应用场景

1. 网络可靠性：识别通信网络中的单点故障和单链路故障
2. 交通路网：找出关键路口和路段，指导冗余建设
3. 社交网络：发现维系社区连通性的关键人物
4. 电力系统：识别电网中的脆弱节点和输电线路
5. 分子生物学：分析蛋白质相互作用网络的关键节点

六、扩展：双连通图的判定与构造

• 点双连通图：无割点的连通图，任意两点间存在至少两条点不相交路径
• 边双连通图：无割边的连通图，任意两点间存在至少两条边不相交路径

通过加边消除所有割点/割边，可将图转化为双连通图，这是网络加固的基础问题。贪心策略是：对每条割边，在其分离的两个连通分量间添加一条新边。