我有一个编程任务（不做作业）。在那里我找到了图中的桥梁。我在它的工作有点自己，但不能拿出任何令人满意的。所以我GOOGLE了它，我确实发现一些东西，但我无法理解的算法，因为它是presented。可能有人请看看这个code，给我一个解释？谢谢。（从segdewick的书它）。谢谢你。

I have a programming task(not homework.) where I have to find the bridges in a graph. I worked on it a bit myself, but could not come up with anything satisfactory. So i googled it , I did find something but I am unable to understand the algorithm as it is presented. Could someone please take a look at this code and give me an explanation.? Thanks.(Its from segdewick's book). Thanks.

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

推荐答案

默认值：桥是边缘，在卸下的情况将断开图形（或增加1连接部件的数量）

Def: Bridge is an edge, when removed, will disconnect the graph (or increase the number of connected components by 1).

对于图中桥一观察;没有一个属于一个环可以是一个桥的边。因此，在图中，如 A - B - C - A ，消除任何边缘 A - B ， B - ç和ç - A 不会断开图。但是，对于一个无向图，边 A - B 意味着 B - A ;而这种优势可能仍然是一个桥梁，其中唯一的循环是在为 A - B - A 。因此，我们应该只考虑那些由后缘形成的环。这是你传递函数参数的家长信息帮助。这将帮助你不使用循环，如 A - B - A 。

One observation regarding bridges in graph; none of the edges that belong to a loop can be a bridge. So in a graph such as A--B--C--A, removing any of the edge A--B, B--C and C--A will not disconnect the graph. But, for an undirected graph, the edge A--B implies B--A; and this edge could still be a bridge, where the only loop it is in is A--B--A. So, we should consider only those loops formed by a back edge. This is where the parent information you've passed in the function argument helps. It will help you to not use the loops such as A--B--A.

现在来识别后缘（或回路）， A - B - C - A 我们使用了低和 pre 阵列。数组 pre 就像访问数组中的DFS算法;而不是只标记了顶点为已访问，我们确定每个顶点具有不同数目但（根据其在DFS树中的位置）。该低阵列有助于确定是否存在一个循环。该低阵列标识最低编号（从 pre 阵列）的顶点，当前顶点可以到达。

Now to identify the back edge (or the loop), A--B--C--A we use the low and pre arrays. The array pre is like the visited array in the dfs algorithm; but instead of just flagging that the vertex as visited, we identify each vertex with a different number (according to its position in the dfs tree). The low array helps to identify if there is a loop. The low array identifies the lowest numbered (from pre array) vertex that the current vertex can reach.

通过这个图让工作 A - B - C - ð - B 。

起始于

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

在这一点上，你遇到了一个循环/循环图中。在您的code 如果（pre [W] == -1）将是错误的这个时候。所以，你会进入else部分。 if语句有检查是否 B 是 D 的父节点。它不是，那么 D 将吸收 B 的 pre 价值为低。继续该示例，

At this point, you've encountered a cycle/loop in graph. In your code if (pre[w] == -1) will be false this time. So, you'll enter the else part. The if statement there is checking if B is the parent vertex of D. It is not, so D will absorb B's pre value into low. Continuing the example,

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

D 此低值传播回 C 通过code 低[V] = Math.min（低[V]，低[W]）; 。

This low value of D propagates back to C through the code 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 的桥梁。在code 低['B'] == pre ['B'] 指边 B 将是一个桥梁。这是因为，我们可以从 B 达到最低顶点 B 本身。

Now, that the cycle/loop is identified, we note that the vertex A is not part of the loop. So, you print out A--B as a bridge. The code low['B'] == pre['B'] means an edge to B will be a bridge. This is because, the lowest vertex we can reach from B is B itself.

希望这有助于解释