问Java - Graph关键链接

EN

这个问题似乎非常类似于在图中查找表达节点的问题。铰接点或双连接组件的技术定义是一个节点，如果删除该节点，将导致图形一分为二。

从图中发现连接节点是一个在很大程度上解决了的问题，您可以在此处找到有关它的更多详细信息：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算法的方法只需要一个警告，即您应该始终将节点连接到要拆分的两个节点。此外，为了能够向后返回到需要剪切的原始边，您应该保留对边最初所属节点的引用。

这里有一个很好的可视化的卡格尔算法：http://en.wikipedia.org/wiki/Karger%27s_algorithm

你想要的是一次最小的s-t削减。在一般图中找到一个的通常方法是使用源0和目标6运行像push relabel这样的算法，该算法计算最小s-t切割作为计算最大流的副产品。

Karger的算法找到了最小割集，即它最小化了s和t以及裁剪。因为s和t是为你固定的，所以Karger的不合适。关节顶点是一个顶点，它的移除会断开图形的连接。您感兴趣的是删除边，而不是顶点。