Kruskal’s算法产生一棵最小生成树
证明：
设T是贪心法产生的解，U是最优解
设e是属于T但不属于U的成本最小的边;换言之,T中成本小于c(e)的边都在U中.
设f是{e}+U产生的环路上不在T中的一条边,
用反证法证明c(f)≥c(e):如果f的成本小于e的成本,贪心法会先于e将f加入到T中,矛盾。所以c(f)>=c(e)。
于是，如果从U中删除f并加入e（剪枝法）,得到的树U'仍然没有环且包含所有节点，并且U'比原来的树更优，这与假设“U是最优解”矛盾。
所以，其实不存在这样的e，即贪心解就是最优解