甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

算法-最小生成树算法

带权图分为有向和无向,无向图的最短路径又叫做最小生成树,有prime算法和kruskal算法;有向图的最短路径算法有dijkstra算法和floyd算法。

最小生成树问题:给定一个连通无向图,寻找一颗无环树,使得树上所有边权值之和最小。

最小生成树的贪心策略的通用方法

问题描述

已知:连通无向图\(G=(V,E)\),权重函数\(w:E \rightarrow R\) 循环不变式:在每边循环之前,A是某颗最小生成树的一个子集。 伪代码

GENERIC-MST(G,w)
A={}
while A does not form a spanning tree // 当A不是一个生成树时
    find an edge(u,v) that is safe for A // 找到一条A的安全边
    A = A ∪ {(u,v)}
return A

注:安全边是指加入A后,不会使得A违反循环不变式。即 A ∪ {(u,v)}也是某颗最小生成树的一个子集

问题:如何寻找安全边

求安全边

定理:设A是图G的某最小生成树的一个子集。设(S,V-S)是图G中尊重集合A的任意一个切割,又设(u,v)是横跨切割(S,V-S)的一条轻量级边,则边(u,v)对于集合A是安全的。

切割:图中的线 切割尊重集合A:集合A中不存在横跨切割的边(如图a中的灰粗线构成的集合) 轻量级边:横跨一个切割的所有边中权重最小的边(不唯一)。

Kruskal和Prim关系

term 集合A 说明 共性
Kruskal 森林 结点是原图结点,安全边是权重最小的连接两个不同分量的边 都是用具体的规则来确定安全边的方法
Prim 安全边是连接A和A之外某个节点的边中权重最小的边

Kruskal算法

寻找安全边:在所有连接两个不同树的边里,找到权重最小的边(u,v)

伪代码

MST-KRUSKAL(G,w)
A={}//A是森林
for each vertex v∈G.V
    MAKE-SET(v)//将集合A初始化为空集,并创建M颗子树,每棵树各含一个结点
sort the edges of G.E into nondecreasing order by weight w //对边按照权重排序
for each edge(u,v)∈G.E,taken in nondecreasing order by weight//按权重顺序遍历边
    if FIND-SET(v)!=FIND-SET(u)//(u,v)不在一棵树
        A= A ∪ {(u,v)}
        UNION(u,v)
return A

时间复杂度

\(O(ElgV)\)

特点

图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.

c++实现(写的很好,一定要看):Kruskal算法

Prim算法

寻找安全边:A总是一颗树。从单一顶点开始,逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。

为了快速选择新边, 在算法执行的过程中,所有不在树A中的结点都存放在一个基于key属性的最小优先队列Q中。

u.key : 连接结点u和中结点的所有边中最小边的权重。 u.π:u在中的父节点

描述

输入:连通图G,边权w,最小生成树的根节点r

初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {}

循环:重复以下操作,直到\(V_{new}=V\)

  1. 在集合E中选取权值最小的边(u,v),其中u是集合Vnew中的元素,而v则是V中没有加入Vnew的顶点;
  2. 将v加入Vnew中,将(u,v)加入Enew中;

输出:使用集合Vnew和Enew来描述所得到的最小生成树。

图例:

伪代码

MST-PRIM(G,w,r)//r是最小生成树的根节点
for each u∈G.V
    u.key=∞ 
    u.π=NIL //u在树中的父节点
r.key=0
Q=G.V
while Q!={}
    u=EXTRACT-MIN(Q)//某条横跨切割(V-Q,Q)的一个轻量级边的端点
    for each v∈G.Adj[u]//遍历u的邻接表
    if v∈Q and w(u,v)<v.key
        v.π=u
        v.key=w(u,v)

时间复杂度

通过邻接矩阵图表示的简易实现中,找到所有最小权边共需O(V2)的运行时间。使用简单的二叉堆与邻接表来表示的话,普里姆算法的运行时间则可缩减为O(E log V),其中E为连通图的边数,V为顶点数。如果使用较为复杂的斐波那契堆,则可将运行时间进一步缩短为O(E + V log V),这在连通图足够密集时(当E满足Ω(V log V)条件时),可较显著地提高运行速度

参考文献

  1. 维基百科