连通图中的桥梁

本文介绍了连通图中的桥梁的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

限时送ChatGPT账号..

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

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.?

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: Bridge 是一条边，当移除时，将断开图(或增加 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--C 和 C--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 我们使用 low 和 pre代码>数组.数组pre类似于dfs算法中的visited数组；但不是仅仅将顶点标记为已访问，我们用不同的编号(根据其在 dfs 树中的位置)标识每个顶点.low 数组有助于识别是否存在循环.low 数组标识当前顶点可以到达的最低编号(来自 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--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 中.继续这个例子，

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 的 low 值通过代码 low[v] = Math.min(low[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 作为桥梁打印出来.代码 low['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.

希望这个解释有帮助.

这篇关于连通图中的桥梁的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！