如何在无向图中找到桥？

Question

给定一个无向图，我怎样才能找到所有的桥？我只找到了Tarjan的算法，看起来比较复杂

似乎应该有多个线性时间解，但我找不到。

Answer 1

Tarjan 的算法是第一个在线性时间内运行的无向图中的桥查找算法。然而，存在更简单的算法，您可以查看其实现 here.

    private int bridges;      // number of bridges
    private int cnt;          // counter
    private int[] pre;        // pre[v] = order in which dfs examines v
    private int[] low;        // low[v] = lowest preorder of any vertex connected to v

    public Bridge(Graph G) {
        low = new int[G.V()];
        pre = new int[G.V()];
        for (int v = 0; v < G.V(); v++) low[v] = -1;
        for (int v = 0; v < G.V(); v++) pre[v] = -1;

        for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1)
                dfs(G, v, v);
    }

    public int components() { return bridges + 1; }

    private void dfs(Graph G, int u, int v) {
        pre[v] = cnt++;
        low[v] = pre[v];
        for (int w : G.adj(v)) {
            if (pre[w] == -1) {
                dfs(G, v, w);
                low[v] = Math.min(low[v], low[w]);
                if (low[w] == pre[w]) {
                    StdOut.println(v + "-" + w + " is a bridge");
                    bridges++;
                }
            }

            // update low number - ignore reverse of edge leading to v
            else if (w != u)
                low[v] = Math.min(low[v], pre[w]);
        }
    }

该算法通过维护 2 个数组 pre 和 low 来完成这项工作。 pre 保存节点的前序遍历编号。所以 pre[0] = 2 意味着在第 3 次 dfs 调用中发现了顶点 0。 low[u] 保存从 u 可达的任何顶点的最小预序号。

每当边 u--v 时，算法都会检测桥接，其中 u 在预序编号中排在第一位，low[v]==pre[v]。这是因为如果我们移除 u--v 之间的边，v 将无法到达 u 之前的任何顶点。因此，删除边缘会将图形拆分为 2 个单独的图形。

如需更详尽的解释，您还可以查看 this answer .

如何在无向图中找到桥？

How can I find bridges in an undirected graph?

algorithm

graph

undirected-graph