我有一个图表，其中有两个节点(0 和 6)，我必须尽可能减少边缘，以便它们不连接。例如在这张图中
作为节点 0 和 6，我必须切割的最少边缘是 2-7 和 3-7。 我的想法是使用 bfs 找到两者之间的最短路径，我找到一个 (0-2-7-6) 但后来我不知道如何找到另一个 (0-3-7-6)。即使那样我也不知道如何选择要切割的边缘。
如果有人能就此事给我一些建议，那就太好了。
最佳答案
这个问题看起来与在图形中寻找关节节点的问题非常相似。关节点或双连通分量的技术定义是一个节点，移除该节点会导致图形一分为二。
从图中发现铰接节点是一个很大程度上已解决的问题，您可以在此处找到有关它的更多详细信息: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 之间只有 3 条边， 6,8 图。
有一个更成熟的算法(阅读:我没有想出一个)称为 Karger 算法可以解决您的问题，尽管需要 n^2 次。
该算法的工作原理是有效地将相邻节点彼此连接起来，直到只有两个节点，然后计算两个节点之间剩余的边数。边的数量就是分割图所需的最小切割数。
在您的问题中实现 Karger 算法的方式只需要注意，您应该始终将节点连接到要拆分的两个节点。此外，为了能够返回到您需要剪切的原始边缘，您应该保留对边缘最初属于哪些节点的引用。
此处有 Karger 算法的出色可视化:http://en.wikipedia.org/wiki/Karger%27s_algorithm
关于Java - 图形关键链接，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16925727/