连接图中的桥

我有一个编程任务（不是家庭作业），我必须在图中找到桥梁。我自己做了一些工作，但无法想出任何令人满意的东西。所以我用谷歌搜索了它，我确实找到了一些东西，但我无法理解它所呈现的算法。有人可以看一下这段代码并给我一个解释吗？

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

Def：桥是一条边，当移除时，将断开图形（或将连接的组件数量增加 1）。

关于图中桥梁的一项观察；属于循环的边都不能是桥。所以在一个图表中，例如A--B--C--A，删除任何边缘A--B, B--C and C--A不会断开图表。但是，对于无向图，边A--B暗示B--A;这条边仍然可以是一座桥，它所在的唯一循环是A--B--A。因此，我们应该只考虑由后沿形成的那些环。这就是您在函数参数中传递的父信息的用处。它将帮助您不使用诸如A--B--A.

现在要识别后边缘（或环），A--B--C--A我们使用low and pre数组。数组pre就像visiteddfs算法中的数组；但我们不是仅仅将顶点标记为已访问，而是用不同的编号（根据其在 dfs 树中的位置）来标识每个顶点。这low数组有助于识别是否存在循环。这low数组标识最低编号（从prearray) 当前顶点可以到达的顶点。

让我们看一下这张图A--B--C--D--B.

从A开始

dfs:   ^                 ^                 ^                 ^              ^
pre:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3--1
graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B
low:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3->1

此时，您已经遇到了图中的循环/循环。在你的代码中if (pre[w] == -1)这次将会是假的。因此，您将输入 else 部分。 if 语句检查 ifB是 的父顶点D。不是这样D会吸收B's pre值转化为low。继续这个例子，

dfs:            ^
pre:   0--1--2--3
graph: A--B--C--D
low:   0--1--2--1   

This low的价值D传播回C通过代码low[v] = Math.min(low[v], low[w]);.

dfs:         ^           ^           ^
pre:   0--1--2--3--1  0--1--2--3--1  0--1--2--3--1
graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B
low:   0--1--1--1--1  0--1--1--1--1  0--1--1--1--1

现在，循环/循环已确定，我们注意到顶点A不是循环的一部分。所以，你打印出A--B作为一座桥梁。代码low['B'] == pre['B']意味着边缘B将是一座桥梁。这是因为，我们可以到达的最低顶点B is B本身。

希望这个解释有帮助。