桥和割点 | Coder

桥

定义

我们首先看一下桥的概念

上面这幅图中，我们称节点 3-5 之间的这条边为桥，它具有什么特点呢? 一旦将这条边去掉，图的联通分量就会发生变化，所以有如下定义：

如果去掉某条边，使得图的联通分量发生变化，那么称这条边为桥。

桥可以看做是图中最脆弱的那条边，如果将交通系统建模为一个图的话，桥就是交通系统中最脆弱的部分，在军事中如果我们知道对方交通系统中的桥，那么我们就可以军事打击这个桥，使得对方的交通系统瘫痪。

寻找桥

如何判断某条边是不是桥，对于下图来说， 0-1 这条边是桥吗?

答案不是，因为去掉 0-1 这条边联通分量的个数没有增加，原因是节点 1 可以通过另一条路径 1->3->2->0 到达 0，所以我们判断某条边是不是桥，就是判断边的两个节点是否有另外一条路径。考虑边 v-w，如果存在另外一条路径，使得节点 v 可以到达节点 w 或者是节点 w 之前的节点，我们就认为 v-w 不是桥，否则没有另外的路径使得节点 v 到达节点 w，我们就认为 v-w 是桥。

为了完成这个判断，我们需要定义两个变量来帮助我们保存信息，一个是 order[] 数组，它保存的是以 DFS 遍历图的顺序，例如 order[0] = 0，表示节点 0 是第 0 个遍历的，order[3] = 2 表示节点 3 是第 2 个遍历的

另一个需要记录的信息是当前节点通过另外一条路径(即不是父节点那条路径)能够达到的顺序最前的节点，使用数组 low 表示，假设节点 2 能够达到最前的节点 0，而 order[0] = 0，所以 low[2] = order[0] = 0，初始 low[i] = order[i]，更新 low 数组有两个时机

节点 v 访问已被遍历过的邻接节点 w 时(该邻接节点不为父节点)，如果 low[w] < low[v]，则更新 low[v] = low[w]

当我们访问到节点 2 时，接着访问节点 2 的邻接节点，访问到节点 0，节点 0 不是它的父亲节点(上一个节点)，而且节点 0 已经被访问过，并且 low[0] < low[2]，所以这个时候更新 low[2] = low[0]，表示节点 2 能通过另一条路径访问第 low[0] 个遍历的节点，即节点 2 能够访问到第 0 个被遍历的节点，即节点 0
访问完邻接节点 w，回到当前节点 v 时，如果邻接节点的 low[w] < low[v]，则更新 low[v] = low[w]

当节点访问完节点 2 回到节点 3 时，此时 low[2] < low[3]，更新 low[3] = low[2] = 0，表示 low[3] 可以从另外一条路径到达第 low[2] = 0 个被遍历的节点，即节点 0

引入了 order 与 low 数组，接着我们可以根据这两个数组判断某条边是不是桥了，当我们遍历完相邻节点 w，来到当前节点 v 时，除了要更新 low[v]，我们还需要对这条边是不是桥进行判断。

我们需要判断 low[w] 与 order[v] 的大小，以此判断是否是桥。首先明确一下二者表示的意义：

low[w] 表示节点 w 能够通过另一条路径能够到达的最前顺序，例如 low[w] = 3 就表示 w 节点能通过另一条路径到达第 3 个被遍历的节点，
order [v] 表示节点 v 是第几个被遍历的

如果 low[w] $\leq$ order[v]，说明 w 能通过另一条路径到达节点 v 或 v 之前被遍历的节点，说明就不是桥，否则就是桥。

import java.util.ArrayList;
import java.util.HashSet;

public class FindEdge {
    private int[] order;
    private int[] low;
    private Graph graph;
    private boolean[] visited;
    private int count = 0;

    // 存储桥
    private ArrayList<int[]> result;

    public FindEdge(Graph graph) {
        this.graph = graph;
        order = new int[graph.V()];
        low = new int[graph.V()];
        result = new ArrayList<>();
        visited = new boolean[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            if (!visited[i]) {
                dfs(i, i);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        low[v] = count;
        order[v] = count;
        count++;

        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
                // 更新 low[v] 时机 1
                low[v] = Math.min(low[v], low[w]);
                // 判断是否是桥
                if (low[w] > order[v]) {
                    result.add(new int[]{v, w});
                }
            } else if (w != parent){
                // 更细 low[v] 时机 2
                low[v] = Math.min(low[w], low[v]);
            }
        }
    }

    public ArrayList<int[]> getResult() {
        return result;
    }
}

割点

定义

割点的定义与桥的定义类似，割点指的是一个节点，如果一旦移除这个节点，会导致图中的联通分量发生变化，那么就称这个节点为割点。

上图中节点 3 与节点 5 为割点，一旦去掉这两个节点之一，图的联通分量的个数就会发生变化。

寻找割点

寻找割点的过程同寻找桥是一样的，也需要维护 order 与 low 两个数组，这两数组的含义也是同上一致的。low 数组的更新时机以及更新过程也是同上一致的。

现在的问题是我们在什么时候判断某节点是不是割点，以及条件是什么。我们在遍历完相邻节点 w，返回到当前节点 v 时，如果 low[w] $\geq$ order[v] 时，就说明它是一个割点。这里的判断条件与桥的判断不同，桥的判断条件是如果 low[w] > order[v] 时，就说明 v-w 这条边是桥，注意多了一个等于号。

low[w] $\geq$ order[v] 表示节点 w 与节点 v 之前被遍历的节点产生连接只能通过节点 v

例如节点 4 通过另外一条路径它最多到达节点 5，无法与节点 5 之前被遍历的节点产生连接。一旦节点 5 被删除，4 就无法访问到节点 0, 1, 2, 3，所以 5 就是割点。

但是添加了等于号之后，这个时候因为任何节点 low[v] $\geq$ order[0]，所以根节点 0 会被认为是割点，但根节点不一定是割点，这个时候我们就需要对根节点分别讨论，判断根节点是不是割点很简单，如果通过 DFS 遍历，根节点有两个相邻节点就说明它是割点

import java.util.ArrayList;
import java.util.HashSet;

public class FindCutPoints {
    private Graph graph;
    private boolean[] visited;
    private int[] order;
    private int[] low;
    private int count = 0;

    private HashSet<Integer> result = new HashSet<>();

    public FindCutPoints(Graph graph) {
        this.graph = graph;

        visited = new boolean[graph.V()];
        order = new int[graph.V()];
        low = new int[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            if (!visited[i]) {
                dfs(i, i);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        order[v] = count;
        low[v] = count;
        count++;

        int child = 0;
        for (int w: graph.adj(v)) {
            child++;
            if (!visited[w]) {
                dfs(w, v);
                low[v] = Math.min(low[v], low[w]);
                if (v != parent && low[w] >= order[v]) {
                    result.add(v);
                }
                if (v == parent && child > 1) {
                    result.add(v);
                }
            } else if (w != parent) {
                low[v] = Math.min(low[v], low[w]);
            }
        }
    }

    public HashSet<Integer> getResult() {
        return result;
    }
}