如何在无向图中找到桥？

Question

给定一个无向图，如何找出所有的桥？我只发现了Tarjan算法，但它似乎相当复杂。

看起来应该有多个线性时间的解决方案，但我找不到任何东西。

- Jakub Arnold

---

Tarjan的算法是为了在有向图中查找强连通分量(SCC)，不确定你想如何将其应用于此处（虽然不确定是否不可能）。 - amit

http://www.geeksforgeeks.org/bridge-in-a-graph/ - Gelldur

Answer 1

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

    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]);
        }
    }

该算法通过维护两个数组pre和low来完成任务。pre保存节点的先序遍历编号。因此，pre [0] = 2表示顶点0在第3次深度优先搜索中被发现。而low [u]保存从u可以到达的任何顶点的最小先序号。

当对于边u-v，其中u在先序编号中排在v之前，且low [v] == pre [v]时，该算法检测到桥。这是因为如果我们删除u-v之间的边，v将无法到达任何在u之前发现的顶点。因此，删除该边将使图分裂成两个独立的图。

要了解更详细的说明，您还可以查看此答案。

- Nikunj Banka

---

嗨Nikunj，我想知道你为什么要称这个算法为Tarjan算法？虽然你发布的算法与原始的Tarjan算法共享相同的“low”和“pre”数组，但Tarjan算法用于在有向图中查找强连通分量。 - Gang Fang

嘿，我在想这个Tarjan桥梁查找算法的时间复杂度是O(V)吗？因为虽然我找不到其他地方的算法，除非被告知我需要在俄罗斯，但据我所知，该算法应该是O(V)或者有些人称之为线性时间...但这看起来并不是这样...那么这不是真正的算法吗？ - user3038404