我们已经看到生成树和切割是密切相关的。这是另一个连接。让我们删除 Kruskal 算法添加到生成树的最后一条边；这将树分成两个组件，从而在图中定义了一个切割 (S,S)。我们能说什么？假设我们正在处理的图是未加权的，并且它的边是随机均匀排列的，以便 Kruskal 算法处理它们。这是一个值得注意的事实：至少有 1/n^2 的概率，(S,S) 是图中的最小割，其中割的大小 (S, S) 是 S 和 S 之间交叉的边数. 这意味着重复该过程 O(n^2) 次并输出找到的最小切割以高概率产生 G 中的最小切割：用于未加权最小切割的 O(mn^2 log n) 算法。
这不取决于通过 Kruskal 算法处理图形的 n^2 种独特方法这一事实吗？我的意思是，如果Kruskal 算法只有3 种独特的方式来处理具有 10 个节点的图，那么重复该过程 n^2 次将不会产生 n^2 独特的“最后一条边”。在唯一的最终切割少于 n^2 个（即少于 n^2 个唯一的“最后边缘”）的情况下，它将如何工作？
如果总共有少于 n^2 条边怎么办？例如，您可以有一个只有 9 条边的 10 个节点的连通图，这意味着无论您重复该算法多少次，您都不会有 n^2 个唯一的“最后一条边”。在这种情况下它将如何工作？
循环遍历每个边缘并检查边缘是否是最小切割不是更容易吗？在 n 个节点的图中，唯一边的最大数量为 n + n-1 + n-2... + 1 条边，小于 n^2。考虑到 n^2 小于 n^2 log n，为什么不直接遍历所有边，因为这样更快？