c++ - 在图形 C++ (BOOST) 中寻找桥梁？

Question

我正在阅读 BOOST 库并注意到他们有一种算法可以在图中找到桥，他们确实有一个可以找到接合点的算法。无论如何，这可以有效地完成吗？

我有一个想法:

1.使用BOOST寻找发音点

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

3. 删除它们并计算连接组件的数量，(我假设我的图最初是完全连接的)，如果它超过 1，我将这条边添加到桥上。

问题:是否有必要将桥连接到铰接点？我只是假设它们是，没有找到任何东西。

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

我的其他方法会更天真并采用 O(v*(V+E))，这是非常糟糕的。

Answer 1

重写整个图表听起来有点慢。您必须检查 Boost 是否将单连接顶点计为关节点。 (如果不是，这会使事情稍微复杂化)。

现在很明显，桥必须是两个关节点之间的边，但并非关节点之间的所有边都一定是桥。考虑由 3 条边连接的 4 个关节点链:A-b-c-D。现在添加一个连接到 b 和 c 的节点 e。外面的两个桥仍然是桥，因此所有 4 个原始节点仍然是关节点，但中间节点不再是桥。

这意味着我们有一个必要但不充分的额外条件:边的两个节点都必须是关节点。这是稍微复杂的地方；如果 Boost 不将单连接节点视为关节点，则必须特殊对待它们。但这仍然很简单；一条边必然是一座桥。

这个额外条件在密集图中非常有效，因为大多数节点都不是关节点。结果，您在尝试更改图形之前剔除了大多数候选边。其次，您不需要测试生成的更改图的组件数。您只需要检查直接切割连接它们的边后两个关节点是否仍然连接。