问题描述
限时送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屋!
更多推荐
[db:关键词]
发布评论