我正在阅读 BOOST 库，注意到他们没有一种算法可以在图中找到桥梁，但他们确实有一个可以找到连接点的算法。无论如何，这可以有效地完成吗？
我有个主意：
1.使用 BOOST 寻找关节点
2.使用out_edges，找到连接每个关节点的所有边
3.删除它们并计算连接组件的数量，（我假设我的图最初是完全连接的），如果它超过 1，我将这条边添加到桥上。
问题：桥是否有必要连接到铰接点？我只是假设他们是，没有网络找不到任何东西。
我也想知道如何解决这个问题。
我的另一种方法会更天真，采用 O(v*(V+E))，这是非常糟糕的。
整个图重写听起来有点慢。您必须检查 Boost 是否将单连接顶点计为关节点。 （如果不是，这会使事情稍微复杂化）。
现在很明显，桥一定是两个铰接点之间的边缘，but并非铰接点之间的所有边缘都一定是桥。考虑由 3 条边连接的 4 个关节点的链：A-b-c-D。现在添加一个连接到 b 和 c 的节点 e。外面的两个桥仍然是桥，因此所有 4 个原始节点仍然是铰接点，但中间的节点不再是桥。
这意味着我们有一个必要但不充分的额外条件：边的两个节点都必须是铰接点。这就是稍微复杂化的地方了；如果Boost不将单连接节点算作关节点，则必须特殊对待它们。但这仍然很简单；这个边缘必然是一座桥梁。
这个额外的条件在密集图中非常有效，因为大多数节点不会是关节点。因此，您在尝试更改图形之前会剔除大多数候选边。其次，您不需要测试生成的更改图的组件数量。您只需要在切割直接连接两个关节点的边缘后检查两个关节点是否仍然连接即可。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
