【算法笔记】贪心法--最小生成树
一.Kruskal算法
思路：
每次在图中选择一条最短的且不构成环的边，重复V-1次得到最小生成树
注：不在一个集合表示不连通，保证了不会形成环
伪代码实现
时间复杂度分析
边排序：O（ElogE）
建立集合：O（V）
查找集合与合并集合O：O（（V+E）logV）
时间复杂度：O（ElogE）
正确性证明 ：
优化子结构：设uv是G中权值最小的边，则必有一棵最 小生成树包含边uv.（反证法）
贪心选择性：按照点的个数进行归纳证明
二.Prim算法
思路：
设置空图G',先将任意顶点加入G‘，每次将G与G’间最短的一条边和对应的顶点加入到G‘中，直到G中没有顶点
伪代码
时间复杂度分析：
O(VlogV+ElogV)=O(ElogV)--使用最小堆实现
正确性证明：
优化子结构： 设uv是G中与顶点u关联的权值最小的边， 则必有一棵最小生成树包含边uv.（反证法）
贪心选择性：归纳证明即可