algorithm - 使无向图断开连接的最小成本

Question

使无向加权（正权重）图断开连接的最小成本是多少。

我的意思是我必须找出那些移除与图形断开连接的边，并且它们的成本最小化。

我有以下想法...

1.找出图中的所有桥梁。那么最小重量的桥边将是ans。

2.如果没有桥意味着所有节点都在一个循环中（我不确定）。然后我根据它们的权重对边缘进行排序，两个最小边缘权重的总和将是 ans。

该图没有自环。

这个算法正确吗？

Answer 1

这个问题看起来与图中“最小切割”的研究回答的问题相同。我建议在此处和此处阅读以下内容，以从图论的角度了解有关它为何起作用的更多信息-该链接还提供了一些伪代码。

关于您提出的算法，在图中找到桥可能会很棘手。您必须检查端点及其局部结构以确认桥的存在。使用边缘收缩可能更容易实现。