来严格证明一下做法
我们利用数学归纳法证明，过程很像“推论+数归证明Kruscal”
假设我们按照书上这么添加后，执行Kruscal
当前执行到\(i\)这条边，已经选上的边都是最开始的树边，已经循环过但没选上的边都是添加的非树边
假设\(i\)是添加的边，那么\(i\)一定不会被选上，因为此时已经选上的边组成了最开始的树的一部分，而导致\(i\)被添加的树边一定已经被遍历过并且选上了，所以\(i\)一定是连接同一连通块中的两点的边，不会被Kruscal选上
假设\(i\)是原来的树边，那么\(i\)一定会被选上，因为根据数学归纳法，我们之前已经被选上了的都是树边，而\(i\)不被选上的原因肯定是因为\(i\)所连接的两点所在的连通块已经被联通了，然后能够完成此操作的必须是被选上的边，由于被选上的都是树边，最开始的树是不可能通过其他树边来完成这个操作的，所以\(i\)不可能不被选上
由以上过程可知，形成MST的过程是唯一的，被选上的一定是最开始给的树边
标签：泼水节,树边,假设,Kruscal,选上,走廊,添加 From： https://www.cnblogs.com/dingxingdi/p/18010799