每日算法 — 使用java实现双连通分量：Tarjan lowlink与图连通性分析

问题引入

在图论中，连通性分析是网络可靠性评估的核心。割点是删除后会增加连通分量数量的顶点，割边（桥）是删除后会增加连通分量数量的边。双连通分量则是没有割点的极大子图，分为点双连通分量（任意两点间存在不经过其他点的路径）和边双连通分量（任意两点间存在不共享边的路径）。本文用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);
    }
}

复杂度分析

Tarjan算法是线性时间算法，效率极高。对于10^5节点、10^6边规模的图，Java实现可在毫秒级完成计算。

关键技巧总结

• low[v] > dfn[u] 中的严格大于号判断割边，等于号判断割点，区别需注意
• 无向图中需跳过父边（通过边编号区分），但不能简单跳过父节点（因可能有重边）
• 根节点割点判定条件为子树数量≥2，与非根节点的low[v] >= dfn[u]不同
• 边双连通分量的提取只需在DFS时避开所有桥即可，无需额外复杂逻辑
• 点双连通分量（点双）需要借助栈在DFS过程中维护路径，实现比边双更复杂