连接图中的桥梁

Question

我有一个编程任务(不是家庭作业.),我必须在图中找到桥梁.我自己做了一些工作,但无法想出任何令人满意的东西.所以我用Google搜索,我找到了一些东西,但我无法理解它所呈现的算法.有人可以看看这段代码并给我一个解释.

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

Answer 1

Def:Bridge是边缘,当删除时,将断开图形(或将连接组件的数量增加1).

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

现在要识别后边缘(或循环),A--B--C--A我们使用low和pre数组.该数组pre类似于visiteddfs算法中的数组; 但是我们不是仅将顶点标记为已访问,而是使用不同的数字(根据其在dfs树中的位置)标识每个顶点.该low阵列有助于识别是否存在循环.该low数组标识pre当前顶点可以到达的最低编号(从数组)顶点.

让我们通过这个图表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语句检查if B是否为父顶点D.它不是,所以D将吸收B的pre价值low.继续这个例子,

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

这个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是B本身.

希望这个解释有所帮助