浅谈Kruskal

· · 个人记录

Kruskal是啥？

百度百科链接在此！

如果看不懂或者懒得点，可以看我下面的介绍。

``` 找出最小的未考虑边edge[i]。 如果edge[i]的两个端点不在同一联通块内就选，否则就不选。 重复执行直到构成生成树。如果边不够选，则图不连通。 ``` ## 很贪心，不是吗？ 那么，这种算法为何是正确的呢？ #### 让我们来反证一下。 如果我们再多选一条边，这时就会构成环。然而，环上其它所有的边都是我们从小到大挑选出来的，显然一定是小于等于我们多选的这一条边。那么，如果将其中一条边替换为这多选的一条，那新的方案不是和原方案等价，就是更劣于原方案。（如果有人不会次小生成树，这给证明过程可以给出一些思路）