0

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

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

我有以下想法...

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

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

该图没有自环。

这个算法正确吗?

4

1 回答 1

0

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

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

于 2012-10-02T19:06:13.513 回答