最小生成树总结

1. 基本原理：

贪心法；通用的算法都是采用这种贪心策略，它在每一个步骤中都形成最小生成树的一条边，算法维护一个变的集合A：保持以下的循环不变式：在每一次循环迭代之前，A是某个最小生成树的一个子集；

2. 基本模式

GENERIC-MST(G,w)
    A = Q
    while A does not form a spanning tree
        find an edge (u,v) that is safe for A
        A = AＵ{(u,v)}
    return A

3. 问题的关键：

寻找安全边（使A = AＵ{(u,v)}仍然是某一个最小生成树子集的边(u,v)）。

4. 寻找安全边的规则：

4.1 基本概念

割：无向图G=(V,E)的一个割(S,V-S)是对V的一个划分。

边通过割：当无向图G的一条边一个端点属于S，而另一个端点属于V-S时，称该边通过割(S,V-S)。

割不妨害边集A：如果一个边的集合A中没有边通过该割。

轻边(light edge)：如果某条边的权值是通过一个割的所有边中最小的，则称该边位通过这个割的一条轻边。另外还有满足某一性质的轻边。

4.2 添加安全边的定理准则

图G=(V,E)是一个无向图且在边E上定义了加权函数值；A是G的某个最小生成树的子集。设割(S,V-S)是任意一个不妨害边集A的割，且边(u,v)是通过该割的一条轻边。则该边对集合A来说是安全的。

理解：

1)边集A的顶点一定全在S或V-S;

2)包含A的最小生成树可能有多棵；

3)集合A始终是无回路的；

4)在算法执行的任一时刻，图G_A=(V,A)是一个森林，G_A的每一个连通分支都是一棵树；

5)算法Generic-MST(G,w)每循环一次确定一条最小生成树的边，共执行|V|-1次；初始时，A=∅，G_A有|V|棵树，每次迭代过程均减少一颗树，当森林只包含一棵树时，算法终止；

6)该定理可以简述为以下MST性质：假设G=(V,E)是一个连通图网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。

5. 分类：

依据通用算法中安全边确定规则细节的不同，分了两种算法：Kruskal和Prim算法

5.1 Kruskal算法

原理：最小生成树子集合A是一个森林，加入集合A中的安全边总是图中连接两个不同联通分支的最小权边；Kruskal算法也是一种贪心算法：算法的每一步中添加到森林中的边的权值都是尽可能小的；

算法：采用了一种不相交集合数据结构，以维护几个互不相交的元素集合：

MST-KRUSKAL(G,W)

//初始化：A为空，并建立|V|棵树，每棵树包含图中一顶点
    A = ∅
    for each vertex v∈G.V
        MAKE-SET(v)
        
    sort the edge(u,v)∈G.E in nondecreasing order by weight w
    
    for edge(u,v)∈G.E, taken in nondecreasing order by weight
        if FIND-SET(u) ≠ FIND-SET(v)
            A = A∪{(u,v)}

算法时间复杂度：O(ElgE)也可以写成O(ElgV)

5.2 Prim算法

原理：集合A仅形成单棵树，添加入集合A的安全边总是连接该树与一个不在树中的顶点的最小权边。因为每次添加到树中的边都是使树的权尽可能小的边，因此，上述策略也是“贪心的”。

算法：

相关数据结构：基于key域（权值w）的最小优先队列Q（存储不在树中所有的顶点）；key[V]:所有与树A某一顶点相连的边的最小权值；π[V]：各顶点的双亲结点；

MST-PRIM(G,w,r)
    
//初始化
    for each u∈G.V
        key[u] = ∞
        π[u] = NIL
    key[r] = 0 //根结点初始化为0，成为第一个被处理的顶点
    Q = V[G]
    
//依次确定添于树A的下一个结点u，即与A相连的不在A的最小权边
    while Q ≠ ∅
            u = EXTRACT-MIN(Q)//找出与通过割(V-Q,Q)的一条轻边相关联的顶点u∈Q（第一次例外）
            for each v∈Adj[u]//u加入A后更新A邻接点的key值
                if v∈Q and w(u,v)<key[v]
                    π[v] = u
                    key[v] = w(u,v)

说明：

1)算法执行过程中，GENERIC-MST的结合A隐含地满足：A={(v,π[v]):v∈V-{r}-Q};当算法终止时，Q是空的，G的最小生成树A={(v,π[v]):v∈V-{r}}；

2)基本原理都知道，实现的关键之一是如何保存已经找到得到最小生成树的子集A，本算法巧妙的利用每个顶点的双亲结点得出A;

3)算法实现的关键之二是利用一个队列记录从A到剩余顶点具有最小代价的边，即割(V(A),V-A)的轻边；

时间复杂度：

算法的初始化部分复杂度为O(V)；剩下的while循环执行|V|次，循环体内有两个操作，依次是提取轻边和修改邻接点key值。这样复杂度就取决于优先队列Q是如何实现（数组、二叉队列及Fibonacci队列）及图的数据结构，根据其不同，可分为如下部分：

Minimum edge weight data structure	Time complexity (total)
Searching, adjacency matrix	O(V²)
binary heap, adjacency list	O((V+E)logV) = O(ElogV)
Fibonacci heap, adjacency list	O(E+VlogV)

参考文献：《算法导论》、严蔚敏《数据结构》