我试图实现Karger的min算法用同样的方式在这里解释,但我不喜欢这样一个事实,即在we循环的每一步,我们都可以在一个超级节点中选择两个端点。更具体地说,这一部分
// If two corners belong to same subset,
// then no point considering this edge
if (subset1 == subset2)
continue; 有快速解决办法来避免这个问题吗?
发布于 2020-05-31 21:58:37
它可能有助于备份和思考为什么这里有一个联盟-查找结构,为什么它是值得改进的继续声明。
从概念上讲,执行的每个收缩都以下列方式更改了图形:
那么,问题是如何对图进行实际操作。你找到的代码懒洋洋地这么做。当收缩完成时,它实际上不会改变图形。相反,它使用联合查找结构来显示哪些节点现在是等价的。当它采样一个随机边时,它必须检查该边是否是步骤(3)中被删除的边之一。如果是这样的话,它就跳过它,然后继续前进。这样做的效果是早期收缩非常快(当很少有边缘收缩时,选择作为收缩节点一部分的两条边的可能性非常低),但后来的收缩可能要慢得多(一旦边缘开始收缩,许多边缘可能被删除)。
这里有一个简单的修改,您可以使用它来加速这一步。每当您选择要收缩的边缘,并发现它的端点已经连接,放弃该边缘,并将其从边缘列表中删除,这样它就不会再被选中。您可以通过将边缘交换到边缘列表的末尾,然后删除列表的最后一个元素来做到这一点。这样做的效果是,每一条处理过的边缘都不会再被看到,所以在算法的所有迭代中,每条边最多只能被处理一次。这给出了一个随机收缩阶段O(m + nα(n))的运行时,其中m是边数,n是节点数。α(n)的因素来自于联合查找结构的使用。
如果您真的想要删除连续语句的所有表象,另一种方法是直接模拟收缩。每次收缩后,遍历所有m个边,并通过查看其是否需要保持不变、指向新的收缩节点或完全删除来调整每个边。这将需要的时间O(m)每收缩的净成本O(mn)的整体最小削减计算。
有一些方法可以让事情变得更快。Karger的原始论文建议生成边的随机排列,并在该数组上使用二进制搜索,巧妙地使用BFS或DFS找到时间O(m)中产生的切线,这比O(m + nα(n))方法对大图的切分略快。其基本思想如下:
每个BFS的代价是O(m),其中m是图中的边数,这给出了递归T(m) = T(m/2) + O(m),因为在每一阶段我们都丢弃了一半的边。这解决了O(m)的总时间,虽然你可以看到,这是一个更复杂的方式编码这个算法!
概括地说:
希望这能有所帮助!
https://stackoverflow.com/questions/62116263
复制相似问题