minimum

图论中最⼩⽣成树（MinimumSpanningTree）

什么是图

通常情况下，我们把图看成是⼀种由“顶点(node)”和“边(arc)”组成的抽象⽹络。

下⾯我们看⼀个⽐较⽼套的通信问题：

在各⼤城市中建设通信⽹络，如下图所⽰，每个圆圈代表⼀座城市，⽽边上的数字代表了建⽴通信连接的价格。那么，请问怎样才能以最⼩

的价格使各⼤城市能直接或者间接地连接起来呢？

我们需要注意两点：

-最⼩的价格

-各⼤城市可以是直接或者间接相连的

题⽬的要求是，城市只需要直接或者间接相连，因此，为了节省成本，我们稍稍优化⼀下上述⽅案如下：

可以看到，我们砍掉了原先在AD，BE之间的两条道路，建设价格⾃然就降下来了。当然这个⽅案也是符合我们题⽬的要求的。

上⾯的实例由于数据很简单，优化的⽅案很easy就看出来了。但在实际中，数据量往往是⾮常庞⼤的。所以，我们更倾向于设计⼀种⽅法，

然后利⽤计算机强⼤的运算能⼒帮我们处理这些数据得出最优的⽅案。

最⼩⽣成树

-对于⼀个图⽽⾔，它可以⽣成很多树，如右侧图2，图3就是由图1⽣成的。

-从上⾯可以看出⽣成树是将原图的全部顶点以最少的边连通的⼦图，对于有n个顶点的连通图，⽣成树有n-1条边，若边数⼩于此数就不可

能将各顶点连通，如果边的数量多于n-1条边，必定会产⽣回路。

-对于⼀个带权连通图，⽣成树不同，树中各边上权值总和也不同，权值总和最⼩的⽣成树则称为图的最⼩⽣成树。

最⼩⽣成树的算法

关于最⼩⽣成树有两种算法：Prim算法和Kruskal算法。

Prim算法

基本思想：

假设有⼀个⽆向带权图G=(V,E)，他的最⼩⽣成树为MinTree=(V,T)，其中V为顶点集合，T为边的集合。

求边的集合T的步骤如下：

①令U={u0}，T={}。其中U为最⼩⽣成树的顶点集合，开始时U中只含有顶点u0（u0可以为集合V中任意⼀项），在开始构造最⼩⽣成树

时我们从u0出发。

②对所有u∈U，v∈(V–U)（其中u,v表⽰顶点）的边(u,v)中，找⼀条权值最⼩的边(u’,v’)，将这条边加⼊到集合T中，将顶点v’加⼊

集合U中。

③直到将V中所有顶点加⼊U中，则算法结束，否则⼀直重复以上两步。

④符号说明：我们⽤⼤写字母表⽰集合，⽤⼩写字母表⽰顶点元素，⽤<>表⽰两点之间的边。

过程：

⑴初始状态：U={a}V={b,c,d,e}T={}（以“a”为初始点）

⑵集合U和V相关联的权值最⼩的边是，于是我们将b加⼊U。U={a,b}，V={d,c,e}，T={}

⑶此时集合U和V相关联的权值最⼩的边是，于是我们将c加⼊U。U={a,b,c}，V={d,e}，T={,}

⑷显然此时集合U和V中相关联的权值最⼩的边是，于是我们将d加⼊U。U={a,b,c,d}，V={e}，T={,,}

⑸最后集合U和V中相关联的权值最⼩的边是，于是将e加⼊U。U={a,b,c,d,e}，V={}，T={,,,}。

到此所有点访问完毕。

Kruskal算法

解最⼩⽣成树的另⼀种常见的算法是Kruskal算法，它⽐Prim算法更直观。

Kruskal算法的做法是：每次都从剩余边中选取权值最⼩的，当然，这条边不能使已有的边产⽣回路。⼿动求解会发现Kruskal算法异常简

单，下⾯是⼀个例⼦

先对边的权值排个序：

1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)、8(V3,V6)、10(V5,V6)、12(V3,V5)、15(V4,V5)、20(V0,V1)

⾸选边1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)，此时的图是这样（从加⼊“8”开始就会产⽣回路）

显然，若选取边8(V3,V6)则会出现环，则必须抛弃8(V3,V6)，选择下⼀条10(V5,V6)没有问题，此时图变成这样

显然，12(V3,V5)同样不可取，选取15(V4,V5)，边数已达到要求，算法结束。最终的图是这样的

算法逻辑很容易理解，但⽤代码判断当前边是否会引起环的出现则很棘⼿。这⾥简单提⼀提连通分量

在⽆向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中

较⼤的连通⼦图称为连通分量。

在有向图中，如果对于每⼀对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极⼤连通⼦图称为强

连通分量。

【算法说明】

为了判断环的出现，我们换个⾓度来理解Kruskal算法的做法：

初始时，把图中的n个顶点看成是独⽴的n个连通分量，从树的⾓度看，也是n个根节点。我们选边的标准是这样的：若边上的两个顶点从

属于两个不同的连通分量，则此边可取，否则考察下⼀条权值最⼩的边。

于是问题⼜来了，如何判断两个顶点是否属于同⼀个连通分量呢？这个可以参照并查集的做法解决。它的思路是：如果两个顶点的根节点

是⼀样的，则显然是属于同⼀个连通分量。这也同样暗⽰着：在加⼊新边时，要更新⽗节点。