我在阅读BOOST库时发现,他们确实有一种算法可以在图中找到桥,而他们确实有一种可以找到铰接点.无论如何,这可以有效地完成吗？

我有个主意：

1.使用BOOST查找连接点

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

3.删除它们,并计算连接的组件上的数量(我假设我的图形最初是完全连接的),如果其数量大于1,则将此边添加到桥上.

问题：是否有必要将桥连接到铰接点？我只是以为他们是,找不到任何东西,没有网.

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

我的另一种方法会更幼稚,采用O(v *(V E)),这是非常糟糕的.

解决方法:

整个图形重写听起来有些慢.您必须检查Boost是否将单个连接的顶点计为铰接点. (如果没有,这会使事情稍微复杂化).

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

这意味着我们有一个必要但不足的额外条件：边缘的两个节点都必须是关节点.这是轻微的并发症介入的地方；如果Boost不将单连接的节点视为连接点,则必须对其进行特殊对待.但这仍然很简单.一条边缘一定是一座桥梁.

这种额外的条件在密集图中非常有效,因为大多数节点将不是关节点.因此,您在尝试更改图形之前会剔除大多数候选边.其次,您无需测试更改后的图形的组件数.您只需要检查两个直接连接的边缘后就可以检查两个铰接点是否仍然连接.