算法导论-上课笔记10:最小生成树

文章目录

• ​​0 前言​​
• ​​1 最小生成树​​
• ​​2 Kruskal算法​​
• ​​3 Prim算法​​

0 前言

在电路设计中，常常需要将多个组件的针脚连接在一起。要连接n个针脚，可以使用n-1根连线，每根连线连接两个针脚，则所使用的连线长度最短就是最佳方案。

可以将上述的布线问题用一个连通无向图G=(V,E)来予以表示，这里的V是针脚的集合，E是针脚之间的可能连接，并且对于每条边(u,v)∈E，为其赋予权重w(u,v)作为连接针脚u和针脚v的代价，即连线的长度。现在的目标是找到一个无环子集T⊆E，既能够将所有的结点(针脚)连接起来，又具有最小的总权重，即：

的值最小。由于T是无环的，并且连通所有的结点，因此T必然是一棵树。称这样的树为图G的生成树，因为它是由图G所生成的。称求取该生成树的问题为最小生成树问题。

MST，Minimum Spanning Tree，即最小生成树。

下图(记为图1)描述的是一个连通图及其最小生成树的例子：

下面详细讨论解决最小生成树问题的两种算法：Kruskal算法和Prim算法，这两种最小生成树算法都用到了贪心算法的思想。贪心算法的每一步必须在多个可能的选择中选择一种。贪心算法推荐选择在当前看来最好的选择。这种策略一般并不能保证找到一个全局最优的解决方案。但是，对于最小生成树问题来说，可以证明，某些贪心策略确实能够找到一棵权重最小的生成树。因为树是图的一种，为了精确起见，在定义树时不仅要用到边，还必须用到结点，树T中的结点是指由T中的边所连接的结点。

1 最小生成树

假定有一个连通无向图G=(V,E)和权重函数w：E→R，目标是找出图G的一棵最小生成树。后面将讨论的两种算法都使用贪心策略来解决这个问题，但它们使用贪心策略的方式却有所不同，该策略可以由下面的通用方法来表述。该通用方法在每个时刻生长(读三声zhang)出最小生成树的一条边，并在整个策略的实施过程中，管理一个遵守下述循环不变式的边集合A：

【在每遍循环之前，A是某棵最小生成树的一个子集】

在每一步，要做的事情是选择一条边(u,v)，将其加入到集合A中，使得A不违反循环不变式，即A∪{(u,v)}也是某棵最小生成树的子集。由于可以安全地将这种边加入到集合A而不会破坏A的循环不变式，因此称这样的边为集合A的安全边。

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

使用循环不变式的方式如下：

• 初始化：在算法第2行之后，集合A直接满足循环不变式。
• 保持：算法第3-5行的循环通过只加入安全边来维持循环不变式。
• 终止：所有加入到集合A中的边都属于某棵最小生成树，因此，算法第6行所返回的集合A必然是一棵最小生成树。

这里的关键是算法的第4行：找到一条安全边。这条安全边必然存在，因为在执行算法第4行时，循环不变式告诉存在一棵生成树T，满足A⊆T。在第3-5行的while循环体内，集合A一定是T的真子集，因此，必然存在一条边(u,v)∈T，使得(u,v)∉A，并且(u,v)对于集合A是安全的。

无向图G=(V,E)的一个切割(S,V-S)是集合V的一个划分，如下图(记为图2)所示：

有：

1、如果一条边(u,v)∈E的一个端点位于集合S，另一个端点位于集合V-S，则称该条边横跨切割(S,V-S)。

2、如果集合A中不存在横跨该切割的边，则称该切割尊重集合A。

3、在横跨一个切割的所有边中，权重最小的边称为轻量级边。注意，轻量级边可能不是唯一的。一般，如果一条边是满足某个性质的所有边中权重最小的，则称该条边是满足给定性质的一条轻量级边。

用来辨认安全边的规则由下面的定理给出。

定理1：设G=(V,E)是一个在边E上定义了实数值权重函数w的连通无向图。设集合A为E的一个子集，且A包括在图G的某棵最小生成树中，设(S,V-S)是图G中尊重集合A的任意一个切割，又设(u,v)是横跨切割(S,V-S)的一条轻量级边。那么边(u,v)对于集合A是安全的。

证明：设T是一棵包括A的最小生成树，并假定T不包含轻量级边(u,v)；否则，已经证明完毕。现在来构建另一棵最小生成树T’，通过剪切和粘贴来将A∪{(u,v)}包括在树T’中，从而证明(u,v)对于集合A来说是安全的。

边(u,v)与T中从结点u到结点v的简单路径p形成一个环路，如图3所示：

由于结点u和结点v分别处在切割(S,V-S)的两端，T中至少有一条边属于简单路径p并且横跨该切割。设(x,y)为这样的一条边。因为切割(S,V-S)尊重集合A，因此边(x,y)不可能在集合A中。由于边(x,y)位于T中从u到v的唯一简单路径上，将该条边删除会导致T被分解为两个连通分量。将(u,v)加上去可将这两个连通分量连接起来形成一棵新的生成树T’=T-{(x,y)}∪{(u,v)}。

下面证明T’是一棵最小生成树。由于边(u,v)是横跨切割(S,V-S)的一条轻量级边并且边(x,y)也横跨该切割，有w(u,v)≤w(x,y)。因此，w(T’)=w(T)-w(x,y)+w(u,v)≤w(T)。但是，T是一棵最小生成树，有w(T)≤w(T’)。此时下面两个式子同时成立：

1、w(T)≤w(T’)；

2、w(T’)≤w(T)。

因此，w(T)=w(T’)，即T’一定也是一棵最小生成树。

还需要证明：边(u,v)对于集合A来说是一条安全边。因为A⊆T并且(x,y)∉A，所以有A⊆T’；因此A∪{(u,v)}⊆T’。由于T’是最小生成树，因此(u,v)对于集合A是安全的。

定理1得证。

定理1能够帮助更好地理解连通图G=(V,E)上算法GENERIC-MST的工作原理。随着该算法的推进，集合A总是保持在无环状态；否则，包含A的最小生成树将包含一个环路，这将与树的定义相矛盾。在算法执行的任意时刻，图G_A=(V,A)是一个森林，G_A中的每个连通分量则是一棵树(某些树可能仅包含一个结点，如在算法开始时，集合A为空，而森林中包含|V|棵树，每棵树中只有一个结点)。而且，由于A∪{(u,v)}必须是无环的，因此所有对于集合A为安全的边(u,v)所连接的是G_A中不同的连通分量。

GENERIC-MST算法的第3-5行的while循环执行的总次数为|V|-1次，因为该循环的每遍循环都找出最小生成树所需|V|-1条边中的一条。在初始时，当A=∅时，G_A中有|V|棵树，每遍循环将树的数量减少1棵。当整个森林仅包含一棵树时，该算法就终止。

推论2：设G=(V,E)是一个连通无向图，并有定义在边集合E上的实数值权重函数w。设集合A为E的一个子集，且该子集包括在G的某棵最小生成树里，并设C=(V_c,E_c)为森林G_A=(V,A)中的一个连通分量(树)。如果边(u,v)是连接C和G_A中某个其他连通分量的一条轻量级边，则边(u,v)对于集合A是安全的。

证明：切割(V_c,V-V_c)尊重集合A，边(u,v)是横跨该切割的一条轻量级边，因此，边(u,v)对于集合A是安全的。

推论2得证。

下面两小节对最小生成树问题的两个经典算法进行讨论。这两种算法都是本节所讨论的通用算法的细化，每种算法都使用一条具体的规则来确定GENERIC-MST算法第4行所描述的安全边。其中：

1、在Kruskal算法中，集合A是一个森林中的边集，森林中的结点就是给定图的结点。每次加入到集合A中的安全边永远是权重最小的连接两个不同分量的边。

2、在Prim算法里，集合A是一棵树中的边集。每次加入到A中的安全边永远是连接A和A之外某个结点的边中权重最小的边。

2 Kruskal算法

Kruskal算法找到安全边的办法是，在所有连接森林中两棵不同树的边里面，找到权重最小的边(u,v)。设C₁和C₂为边(u,v)所连接的两棵树。由于边(u,v)一定是连接C₁和其他某棵树的一条轻量级边，推论2隐含说明了边(u,v)是C₁的一条安全边。很显然，Kruskal算法属于贪心算法，因为它每次都选择一条权重最小的边加入到森林。

Kruskal算法使用一个并查集来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树。操作FIND-SET(u)用来返回包含元素u的集合的代表元素。可以通过测试FIND-SET(u)是否等于FIND-SET(v)来判断结点u和结点v是否属于同一棵树。Kruskal算法使用UNION过程来对两棵树进行合并。Kruskal算法的伪代码如下：

MST-KRUSKAL(G,w)
    A=∅
    for each vertex v∈G.V
        MAKE-SET(v)
    sort the edge 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(v)
            A=A∪{(u,v)}
            UNION(u,v)
    return A

下图(记为图4)描述的是Kruskal算法的工作过程：

Kruskal算法的第2-4行将集合A初始化为一个空集合，并创建|V|棵树，每棵树仅包含一个结点。算法第6-9行的for循环按照权重从低到高的次序对每条边逐一进行检查。对于每条边(u,v)来说，该循环将检查端点u和端点v是否属于同一棵树。如果是，该条边不能加入到森林里(否则将形成环路)。如果不是，则两个端点分别属于不同的树，算法第8行将把这条边加入到集合A中，第9行则将两棵树中的结点进行合并而使得变成一棵树。

对于图G=(V,E)，Kruskal算法的运行时间依赖于并查集的实现方式。假定使用并查集森林实现，并增加按秩合并和路径压缩的功能，则算法第2行对集合A的初始化时间为O(1)，稍后马上会讨论算法第3-4行for循环中的|V|个MAKE-SET操作的代价，第5行对边进行堆排序的时间为O(E·lgE)。算法第6-9行的for循环执行O(E)个FIND-SET和UNION操作。

(上面的可以看懂，下一段我不懂了)

与|V|个MAKE-SET操作一起，这些操作的总运行时间为O((V+E)α(V))，这里α是一个增长非常缓慢的函数。由于假定图G是连通的，因此有|E|≥|V|-1，所以并查集操作的时间代价为O(E·α(V))。又由于α(|V|)=O(lgV)=O(lgE)，Kruskal算法的总运行时间为O(E·lgE)。又有|E|<|V|²，则有lg|E|=O(lgV)，因此Kruskal算法的时间重新表示为O(E·lgV)。

3 Prim算法

与Kruskal算法类似，Prim算法也是之前通用最小生成树算法的一个特例。Prim算法所具有的一个性质是集合A中的边总是构成一棵树。这棵树从一个任意的根结点r开始，一直长大到覆盖V中的所有结点时为止。算法每一步在连接集合A和A之外的结点的所有边中，选择一条轻量级边加入到A中。根据推论2，这条规则所加入的边都是对A安全的边。因此，当算法终止时，A中的边形成一棵最小生成树。本策略也属于贪心策略，因为每一步所加入的边都必须是使树的总权重增加量最小的边。

为了有效地实现Prim算法，需要一种快速的方法来选择一条新的边，以便加入到由集合A中的边所构成的树里。在下面的伪代码中，连通图G和最小生成树的根结点r将作为算法的输入。在算法的执行过程中，所有不在树A中的结点都存放在一个基于key属性的最小优先队列Q中。对于每个结点v，属性v.key保存的是连接v和树中结点的所有边中最小边的权重。规定如果不存在这样的边，则v.key=∞。属性v.π给出的是结点v在树中的父结点。Prim算法将GENERIC-MST中的集合A维持在A={(v,v.π)：v∈V-{r}-Q}的状态下。当Prim算法终止时，最小优先队列Q将为空，而G的最小生成树的边集A则是：A={(v,v.π)：v∈V-{r}}。Prim算法的伪代码如下：

MST-PRIM(G,w,r)
    for each u∈G.V
        u.key=∞
        u.π=NIL
    r.key=0
    Q=G.V
    while Q≠∅
        u=EXTRACT-MIN(Q)
        for each v∈G.Adj[u]
            if v∈Q and w(u,v)<v.key
                v.π=u
                v.key=w(u,v)

如下图(记为图5)：

图5是在图1上执行Prim算法的过程。初始的根结点为a。加阴影的边和黑色的结点都属于树A。在算法每一步，树中的结点就决定了图的一个切割，横跨该切割的一条轻量级边被加入到树中。例如，在图中的第2步，该算法可以选择将边(b,c)加入到树中，也可以选择将边(a,h)加入到树中，因为这两条边都是横跨该切割的轻量级边。

MST-PRIM算法第2-6行将每个结点的key值设置为∞(除根结点r以外，根结点r的key值设置为0，以便使该结点成为第一个被处理的结点)，将每个结点的父结点设置为NIL，并对最小优先队列Q进行初始化，使其包含图中所有的结点。该算法维持的循环不变式由3个部分组成，具体阐述如下。

在算法第7-12行的while循环的每遍循环之前，有：

1、A={(v,v.π)：v∈V-{r}-Q}。

2、已经加入到最小生成树的结点为集合V-Q。

3、对于所有的结点v∈Q，如果v.π≠NIL，则v.key<∞并且v.key是连接结点v和最小生成树中某个结点的轻量级边(v,v.π)的权重。

算法第8行将找出结点u∈Q，该结点是某条横跨切割(V-Q,Q)的轻量级边的一个端点(第1次循环时例外，此时因为算法的第5行，所以有u=r)。接着将结点u从队列Q中删除，并将其加入到集合V-Q中，也就是将边(u,u.π)加入到集合A中。算法第9-12行的for循环将每个与u邻接但却不在树中的结点v的key和π属性进行更新，从而维持循环不变式的第3部分成立。

Prim算法的运行时间取决于最小优先队列Q的实现方式。如果将Q实现为一个二叉最小优先队列，可以使用BUILD-MIN-HEAP来执行算法的第2-6行，时间成本为O(V)。while循环中的语句一共要执行|V|次，由于每个EXTRACT-MIN操作需要的时间成本为O(lgV)，因此EXTRACT-MIN操作的总时间为O(V·lgV)。由于所有邻接链表的长度之和为2|E|，算法第9-12行的for循环的总执行次数为O(E)。在for循环里面，可以在常数时间内完成对一个结点是否属于队列Q的判断，方法就是对每个结点维护一个标志位来指明该结点是否属于Q，并在将结点从Q中删除的时候对该标志位进行更新。算法第12行的赋值操作涉及一个隐含的DECREASE-KEY操作，该操作在二叉最小堆上执行的时间成本为O(lgV)。因此，Prim算法的总时间代价为O(V·lgV+E·lgV)=O(E·lgV)。从渐近意义上来说，它与Kruskal算法的运行时间相同。

END