破圈法

我最近复习数据结构的时候，看到有道习题提到了“破圈法”，这是一种求解最小生成树的方法。

下面是一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。试判断这种方法是否正确。若正确，说明理由；若不正确，举出反例（注：圈就是回路）。

【解答】

这种方法是正确的。

经过“破圈法”之后，最终没有回路，因此一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为 \(T\)，假设 \(T\) 不是最小生成树，则必然存在最小生成树 \(T_0\)，使得它与 \(T\) 的公共边尽可能多，则将 \(T_0\) 与 \(T\) 取并集，得到一个图，此图中必然存在回路，“破圈法”的定义就是从回路中去除权最大的边，因此此时生成的 \(T\) 的权必然是最小的，这与原假设矛盾，从而 \(T\) 是最小生成树。下图说明了“破圈法”的过程:

我隐约感觉这种方法是正确的，可惜没有办法给出严谨证明，而且答案给的证明过程也没有看懂。ChatGPT 也给出了一种证明，可惜我也没有看懂。幸好这是一道模拟题，证不出来也没关系，考试肯定不会考这种题。不过，真正让我产生兴趣的并不是对“破圈法”的证明，而是这种方法的来历。

我记得数据结构和离散 2¹ 都讲过最小生成树，但是不记得有讲过“破圈法”这种方法。

于是我试着在网上查找资料。可惜的是，网上查到的资料都是介绍方法本身和例题解法的，并没有解释这个方法是怎么来的。

维基百科介绍了四种求解最小生成树的经典算法，分别是：

1. Borůvka 算法：第一个求解最小生成树的算法。看了一下，没有看懂。
2. Prim 算法：经典算法，不解释。
3. Kruskal 算法：同样是经典算法，不解释。
4. 反向删除算法：这个算法与 Kruskal 算法相反。它从原始图出发，从大到小遍历所有的边，在保证图连通的情况下断开权重尽可能大的边。

里面并没有“破圈法”。

唯一有价值的线索来自百度百科，上面说这个方法是由管梅谷于 1975 年在《数学的实践与认识》期刊中提出的，还附上了参考资料。不过考虑到百度百科的可信度约等于没有，这种说法肯定不能直接采纳。

于是我决定自己去知网查一查。我试着在知网上搜索“破圈法”，按发表时间正序排列，没想到确实找着了这篇文章。（虽然我现在大部分账号都被注销了，但是还能通过图书馆登录知网，下载论文。）

论文开篇先用一句话概括了这个方法：“任取一个圈，去掉圈上最长的边”。随后给出了完整证明（可惜我还是没看懂）。最后，作者解释了这种方法在他心目中的优点：

破圈法具有便于普及推广的优点。虽然已知的求最小树的另几种方法也不难，但我觉得对于掌握数学知识不很多的实际工作者来说，破圈法可能更容易接受些。

另外，对于不少问题，用破圈法来计算较快。一般说来，若图 \(G\) 是平面图（这种情况在实际问题中还是经常遇到的），则在图上用破圈法算都是较快的。

破圈法还有一个优点，就是当遇到图上有很多圈时，可以几个人合作，分工来计算，算起来就更快些。

不过这个方法的复杂度实在是太高了，小数据量手工计算还可以接受，写成代码什么的还是算了。（我没有算具体的复杂度，感兴趣的同学可以算一下。）

想到 2506 的小东西们刚学完数据结构，我把我的考证成果发到了 2506 水群里。

很快就有学弟指出：这种方法的应用价值不大，光是找圈就不好找（复杂度太高）。确实。

随后又有学弟指出，这个算法实在是太冷门了，“比某 B 开头的算法还冷门”——幸好我刚查过资料，所以知道他指的是 Borůvka 算法。为此我还特意重新打开维基百科，花时间理解了一下这个算法。理解以后感觉这个算法和 Kruskal 算法比较相似，但复杂度不如 Kruskal。这么冷门的算法都听说过，不愧是 OI 佬。

这位学弟还说：“图拟阵²的性质就是好，爱怎么贪心就怎么贪心，能发明一万种算法（”

最后还有学弟提醒，数据结构和离散 2 都讲过最小生成树，但他们也记不清有没有提到破圈法了。于是我去翻了一下 PPT：

• 数据结构只讲了 Prim 和 Kruskal 两种算法，而且都是浅尝辄止——讲 Kruskal 算法的时候甚至没有讲并查集。
• 离散 2 讲了“避圈法”和“破圈法”两种算法，其中“避圈法”的实现与 Kruskal 算法相同。（其实 Prim 算法和 Kruskal 算法都属于“避圈法”）

最后有学弟对我表示感谢。他说虽然破圈法看起来显然成立，但是严谨证明起来真不容易。不用谢！能帮到你们真是太好了。