在图C ++（BOOST）中查找网桥？ [英] Finding Bridges in a graph C++ (BOOST)?

问题描述

我正在阅读BOOST库，发现他们有一种算法可以在图中找到桥梁，他们确实有一个找到关节点。有没有反正这可以有效地完成？

我有一个想法：

1。使用BOOST查找关节点

2。使用out_edges，关节点

3. 删除它们并计算连接组件上的数量（我假设我的图形最初是完全连接的）比1大，我把这个边缘添加到桥梁。

问题：桥梁是否需要连接到关节点？我只是假设他们是，找不到任何网络。

我还想知道如何处理这个问题。

我的另一种方法会更幼稚，并且采取O（v *（V + E）），这是非常糟糕的。

解决方案

整个图形重写听起来有点慢。您必须检查Boost是否计算单连接顶点作为关节点。 （如果没有，这会使事情稍微复杂一些）。

现在很明显，一座桥必须是两个关节点之间的边缘，但关节点之间的所有边缘不一定是桥梁。考虑由3个边连接的4个关节点链：A-b-c-D。现在添加一个连接到b和c的节点。外部的两座桥梁仍然是桥梁，所以所有4个原始节点保持铰接点，但中间节点不再是一座桥梁。

这意味着我们有必要但不足额外条件：边缘的两个节点必须是关节点。这是轻微复杂的步骤;如果Boost不将单连接节点计算为关节点，则必须特别对待它们。但这仍然很简单。一个边缘必然是一座桥梁。

这个额外的条件在稠密图中是非常有效的，因为大多数节点不会是关节点。因此，在尝试更改图形之前，请先挑选出大多数候选边缘。其次，你不需要测试结果改变图的组件数。你只需要检查直接链接它们的边缘后，两个关节点是否仍然连接。

I was reading through the BOOST library and noticed that they dint have an algorithm to find bridges in a graph, they do have one to find articulation points. Is there anyway this could be done efficiently?

I have an idea:

1. Use the BOOST to find articulation points

2. Using out_edges,find all edges attached the each articulation point

3. remove them and calculate the number on connected components,( I assume my graph is originally fully connected), if its more than 1,i add this edge to the bridges.

QUESTION: Is it necessary for bridges to be attached to articulation points? I just assumed they are,couldn't find anything no the net.

I would also like an idea how to approach this.

My other approach would be more naive and take O(v*(V+E)), which is very bad.

解决方案

Sounds a bit slow with the whole graph rewriting. You'd have to check if Boost counts a single-connected vertex as an articulation point. (If not, this slightly complicates things).

Now it is fairly obvious that a bridge must be an edge between two articulation points, but not all edges between articulation points are necessarily bridges. Consider a chain of 4 articulation points connected by 3 edges: A-b-c-D. Now add a node e connected to both b and c. The outer two bridges remain bridges, and so all 4 original nodes remain articulation points, but the middle node is no longer a bridge.

This means we have a necessary but insufficient extra condition: both nodes of the edge must be articulation points. Here's where the slight complication steps in; if Boost doesn't count single-connected nodes as articulation points, you have to treat them specially. But that's still simple; that one edge is necessarily a bridge.

This extra condition is quite efficient in dense graphs, as most nodes will not be articulation points. As a result, you cull most candidate edges before trying to alter the graph. Secondly, you don't need to test the component count of the resulting altered graph. You just need to check if the two articulation points are still connected after you cut the edge linking them directly.

这篇关于在图C ++（BOOST）中查找网桥？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！