【算法笔记】贪心法--最小生成树

一.Kruskal算法

思路:

每次在图中选择一条最短的且不构成环的边,重复V-1次得到最小生成树

注:不在一个集合表示不连通,保证了不会形成环

伪代码实现

img

时间复杂度分析

边排序:O(ElogE)

建立集合:O(V)

查找集合与合并集合O:O((V+E)logV)

时间复杂度:O(ElogE)

正确性证明 :

优化子结构:设uv是G中权值最小的边,则必有一棵最 小生成树包含边uv.(反证法)

贪心选择性:按照点的个数进行归纳证明

二.Prim算法

思路:

设置空图G',先将任意顶点加入G‘,每次将G与G’间最短的一条边和对应的顶点加入到G‘中,直到G中没有顶点

伪代码

img

时间复杂度分析:

O(VlogV+ElogV)=O(ElogV)--使用最小堆实现

正确性证明:

优化子结构: 设uv是G中与顶点u关联的权值最小的边, 则必有一棵最小生成树包含边uv.(反证法)

贪心选择性:归纳证明即可