假设已经通过Kruskal得到一个树，质疑其是否为最小生成树，那么能否通过替换某条边使得边的权值和更小呢？
证明转化为：“在Kruskal得到的树上添一条边e1，因为e1而形成的环中，e1是权值最大的。”
考虑Kruskal的操作过程，当加入某条边e2会导致形成环C时，就舍弃e2。由于Kruskal选择边的过程中，边的权值必然是升序的，所以e2是C中所有边权值最大的。
由此可以说明Kruskal的正确性。
该证明只是为了想通这个算法，并不够严谨。如有错误，还望指正！
版权声明：本文为qq_41892068原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。