【算法笔记】贪心法--最小生成树
一.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.(反证法)
贪心选择性:归纳证明即可