Java - 图形关键链接

Question

我有一个图表,其中我有两个节点(0和6),我必须尽可能削减最小边缘,以便它们不连接.例如,在此图中

作为节点0和6,我必须切割的最小边是2-7和3-7.我的想法是找到两者之间使用bfs的最短路径,我找到一个(0-2-7-6),但后来我不知道如何找到另一个(0-3-7-6).即便如此,我也不知道如何选择切边.

如果有人能就这件事给我一些指示,那就太好了.

Answer 1

这个问题看起来与在图中查找连接节点的问题非常相似。铰接点或双连接组件的技术定义是一个节点，其删除将导致图一分为二。

从图中发现铰接节点是一个很大程度上已解决的问题，您可以在此处找到有关它的更多详细信息： http: //en.wikipedia.org/wiki/Biconnected_component

在我看来，一般来说，您想要解决这样的问题的方式应该是这样的：

1. Find all articulation points
2. Do a bfs from each node and determine articulation points along the path
3. Split graph at the articulation point, choosing the side with minimal edges
4. Continue until the two nodes are not connected

在上面的示例中，7 是唯一的铰接点，因此您可以剪掉 7、2 和 3 之间的边，因为 7 和 0-4 图形之间只有两条边，7 和 5、6、8 之间只有 3 条边图形。

有一种更成熟的算法可以做到这一点（请阅读：我没有想到的算法），称为 Karger 算法，它可以解决您的问题，尽管需要 n^2 时间。

该算法的工作原理是有效地将相邻节点相互连接，直到只剩下两个节点，然后计算两个节点之间剩余的边数。边的数量就是分割图所需的最小切割数。

在问题中实现 Karger 算法的方法只需要注意，您应该始终将节点连接到要拆分的两个节点。此外，为了能够返回到需要剪切的原始边缘，您应该保留对边缘最初属于哪些节点的引用。

这里有 Karger 算法的可视化效果：http://en.wikipedia.org/wiki/Karger%27s_algorithm