连接图中的桥梁

一尘不染

连接图中的桥梁

algorithm

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

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

阅读 279

2020-07-28

共1个答案

一尘不染

定义：桥是一个边，如果删除它，将断开图形连接（或将连接的组件数增加1）。

关于图中桥梁的一种观察；属于环路的边都不能是桥。因此，在诸如的图形中A--B--C--A，删除任何边A--B，B--C并C-- A不会断开图形的连接。但是，对于一个无向图，该边A--B暗示B--A；并且此边缘仍可能是一座桥梁，唯一的循环就是A--B-- A。因此，我们应该只考虑由后边缘形成的那些循环。这是您在function参数中传递的父信息所提供的帮助。这将帮助您不要使用诸如的循环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语句检查是否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自身。

希望这种解释有所帮助。

2020-07-28