在图C++（BOOST）中查找桥梁？

我正在阅读BOOST库，发现他们有一个算法来查找图中的桥，他们确实有一个找到关节点。无论如何，这可以有效地完成？在图C++（BOOST）中查找桥梁？

我有一个想法：

使用升压找到铰接点

2.使用out_edges，找到所有边缘连接的每个关节点

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

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

我也想知道如何解决这个问题。

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

来源

2014-11-24 LoveMeow

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

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

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

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

来源

2014-11-24 13:45:40 MSalters

林一点不清楚，所以你说我只需要检查边缘的整个末端都是关节点？ – LoveMeow 2014-11-24 13:49:50

@LoveMeow：尝试使用具有两个节点和一个边的平凡图。如果Boost将两个节点都算作关节节点，那么是的。如果Boost不把它们算作关节节点，那么你需要对图进行预处理（但效率更高）。迭代地，枚举所有单连接的节点，将它们的单边标记为桥，删除该边并再次检查。（这反复修剪线性链，其中所有的边缘都是桥梁） – MSalters 2014-11-24 14:00:52

我检查了，boost并没有在关节点上对它们进行计数！所以我需要枚举所有连接到一个边的节点，并将它们标记为桥，除了两个关节点之间的那些节点？ – LoveMeow 2014-11-24 14:13:39

当你意识到如果一个双连通元件只包含一条边，这条边就是一座桥，那么有一种更简单的方法。这是很容易使用boost（http://www.boost.org/doc/libs/1_58_0/libs/graph/example/biconnected_components.cpp）来实现：

计算双连通分支
创建为每个组件边缘计数器。Iteratate在所有的边缘和在所有的边缘再次
迭代增加各组分的coresponding边缘计数器，并检查相应的部件的边缘计数器为1，如果这样该边缘是一个桥

来源

2016-10-15 15:10:21 user307380

在图C++（BOOST）中查找桥梁？

回答

相关问题