使用联合查找数据结构修复 Karger 的最小割算法
Fixing Karger's min cut algorithm with union-find data structure
我试图实现 Karger 的最小切割算法 in the same way it is explained here 但我不喜欢这样一个事实，即在 while 循环的每一步我们都可以选择一条边，它的两个端点已经在超节点中。更具体地说，这部分
// If two corners belong to same subset,
// then no point considering this edge
if (subset1 == subset2)
continue;
是否有避免此问题的快速修复方法？
备份并思考为什么这里有联合查找结构以及为什么值得改进 continue 语句可能会有所帮助。
从概念上讲，执行的每次收缩都会按以下方式更改图形：
- 已签约的节点被替换为单个节点。
- 关联到任一节点的边被替换为新联合节点的边。
- 前面两个节点之间的边 运行 被删除。
那么，问题是如何对图表实际执行此操作。您找到的代码懒惰地执行此操作。当收缩完成时，它实际上并没有改变图表。相反，它使用 union-find 结构来显示哪些节点现在彼此等效。当它对随机边进行采样时，它必须检查该边是否是在步骤 (3) 中删除的边之一。如果是这样，它会跳过它并继续前进。这具有早期收缩非常快的效果（当很少有边缘收缩时，选择作为收缩节点一部分的两条边的可能性非常低），但后来的收缩可能会慢得多（一旦边缘开始收缩，很多的边缘可能已被删除）。
这里有一个简单的修改，您可以用来加快这一步。每当您选择要收缩的边并发现其端点已经连接时，丢弃该边，并将其从边列表中删除，这样它就不会被再次选中。您可以这样做通过将该边交换到边列表的末尾，然后删除列表的最后一个元素。这会导致处理过的每条边都不会再出现，因此在算法的所有迭代中，每条边最多处理一次。这给出了一个随机收缩阶段的运行时间为 O(m + nα(n))，其中 m 是边数，n 是节点数。 α(n)的因子来自联合查找结构的使用。
如果您真的想删除该 continue 语句的所有外观，另一种方法是直接模拟收缩。每次收缩后，遍历所有 m 条边并通过查看是否需要保持不变、指向新的收缩节点或完全删除来调整每条边。每次收缩需要 O(m) 的时间，总最小切割计算的净成本为 O(mn)。
有很多方法可以加快速度。 Karger 的原始论文建议生成边缘的随机排列，并巧妙地使用 BFS 或 DFS 在该数组上使用二进制搜索来找到在时间 O(m) 内产生的切割，这比 O(m + nα( n)) 大图的方法。基本思路如下：
- 探测边列表的中间元素。
- 运行只用那些边形成的图上的BFS，看看是否恰好有两个连通分量。
- 如果是这样，太好了！那两个抄送就是你想要的。
- 如果只有一个CC，则丢弃边数组的后半部分，然后重试。
- 如果有多个 CC，将每个 CC 收缩为一个节点，并更新全局 table 指示每个节点属于哪个 CC。然后丢弃数组的前半部分并重试。
每个 BFS 的成本是 O(m)，其中 m 是图中边的数量，这给出了递归 T(m) = T(m/2) + O(m)因为在每个阶段我们都会丢掉一半的边。这解决了 O(m) 总时间，但如您所见，这是一种更复杂的算法编码方式！
总结：
对提供的代码进行非常小的修改，您可以保留 continue 语句，但仍然可以非常快速地实现随机收缩算法。
为了在不牺牲算法运行时间的情况下消除 continue，您需要进行一些大手术，并改变方法以比保持 continue 快一点点渐近。
希望对您有所帮助！
我试图实现 Karger 的最小切割算法 in the same way it is explained here 但我不喜欢这样一个事实，即在 while 循环的每一步我们都可以选择一条边，它的两个端点已经在超节点中。更具体地说，这部分
// If two corners belong to same subset,
// then no point considering this edge
if (subset1 == subset2)
continue;
是否有避免此问题的快速修复方法？
备份并思考为什么这里有联合查找结构以及为什么值得改进 continue 语句可能会有所帮助。
从概念上讲，执行的每次收缩都会按以下方式更改图形：
- 已签约的节点被替换为单个节点。
- 关联到任一节点的边被替换为新联合节点的边。
- 前面两个节点之间的边 运行 被删除。
那么，问题是如何对图表实际执行此操作。您找到的代码懒惰地执行此操作。当收缩完成时，它实际上并没有改变图表。相反，它使用 union-find 结构来显示哪些节点现在彼此等效。当它对随机边进行采样时，它必须检查该边是否是在步骤 (3) 中删除的边之一。如果是这样，它会跳过它并继续前进。这具有早期收缩非常快的效果（当很少有边缘收缩时，选择作为收缩节点一部分的两条边的可能性非常低），但后来的收缩可能会慢得多（一旦边缘开始收缩，很多的边缘可能已被删除）。
这里有一个简单的修改，您可以用来加快这一步。每当您选择要收缩的边并发现其端点已经连接时，丢弃该边，并将其从边列表中删除，这样它就不会被再次选中。您可以这样做通过将该边交换到边列表的末尾，然后删除列表的最后一个元素。这会导致处理过的每条边都不会再出现，因此在算法的所有迭代中，每条边最多处理一次。这给出了一个随机收缩阶段的运行时间为 O(m + nα(n))，其中 m 是边数，n 是节点数。 α(n)的因子来自联合查找结构的使用。
如果您真的想删除该 continue 语句的所有外观，另一种方法是直接模拟收缩。每次收缩后，遍历所有 m 条边并通过查看是否需要保持不变、指向新的收缩节点或完全删除来调整每条边。每次收缩需要 O(m) 的时间，总最小切割计算的净成本为 O(mn)。
有很多方法可以加快速度。 Karger 的原始论文建议生成边缘的随机排列，并巧妙地使用 BFS 或 DFS 在该数组上使用二进制搜索来找到在时间 O(m) 内产生的切割，这比 O(m + nα( n)) 大图的方法。基本思路如下：
- 探测边列表的中间元素。
- 运行只用那些边形成的图上的BFS，看看是否恰好有两个连通分量。
- 如果是这样，太好了！那两个抄送就是你想要的。
- 如果只有一个CC，则丢弃边数组的后半部分，然后重试。
- 如果有多个 CC，将每个 CC 收缩为一个节点，并更新全局 table 指示每个节点属于哪个 CC。然后丢弃数组的前半部分并重试。
每个 BFS 的成本是 O(m)，其中 m 是图中边的数量，这给出了递归 T(m) = T(m/2) + O(m)因为在每个阶段我们都会丢掉一半的边。这解决了 O(m) 总时间，但如您所见，这是一种更复杂的算法编码方式！
总结：
对提供的代码进行非常小的修改，您可以保留 continue 语句，但仍然可以非常快速地实现随机收缩算法。
为了在不牺牲算法运行时间的情况下消除 continue，您需要进行一些大手术，并改变方法以比保持 continue 快一点点渐近。
希望对您有所帮助！