BGL -确定所有的最小值
BGL -确定所有的最小值
提问于 2015-10-15 12:53:13
给出一个图，我想找出所有的边(如果有的话)，如果删除它，就会把图溢出到两个组件中。
最初的想法是给所有的边分配一个1的权重，然后计算出图的最小值。迷你>1意味着没有单一的边缘，当删除时，会导致分裂。
对于最小割集== 1，如果算法能够为它所包含的每一个最小切边提供服务，那就太好了。
不幸的是，BGL似乎不支持这种做法：
stoer_wagner_min_cut函数精确地决定了其中的一个最小裁剪以及它的权重。
(cut.html)
是否有办法使这个工作(即确定一个以上的最小切割)与BGL或我必须想出一些不同的？
回答 1
Stack Overflow用户
发布于 2016-09-11 13:36:33
可能来得有点晚..。
据我所见，您只需要找到图中不属于任何循环的所有边(假设图已经连接)。
这可以通过迭代地删除叶节点(以及连接到它们的边)来完成，就像在拓扑排序中所做的那样，直到没有叶节点，即剩下的图中的每个边都属于至少一个循环。在此过程中删除的所有边缘将是您想要的。
在伪代码中，对于连接的无向图G=(V,E)，可以这样做：
S = Ø
while(there exists a node n∈V s.t. degree(n)==1)
e = edge connected to n
S = S∪{e}
E = E-{e}
V = V-{n}
return S它可以在O(|V|+|E|)时间内完成
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33149112
复制相关文章
相似问题
腾讯云开发者
