最小生成树算法过程详解（信息系统项目管理师考试）

最小生成树算法过程详解

针对最小生成树算法这一知识点，相当一部分课本和相关参考书对算法过程讲解并不是特别详尽。本文主要针对信息系统项目管理师考试，对最小生成树算法过程进行逐步解析，以更加促进对知识点的理解和掌握。

1.概念

在连通的带权图的所有生成树中，权值和最小的那棵生成树（包含图中所有顶点的树）称作最小生成树（权值：在数据结构领域，权值是树或者图中两个结点路径上的值，这个值表明一种代价，如从一个结点到达另外一个结点的路径的长度、所花费的时间、付出的费用等）。

2.带权连通无向图的最小生成树算法

（1）普里姆（Prim）算法

设已知G=(V,E)是一个带权连通无向图，U为构造生成树过程中已被考虑在生成树上的顶点的集合，顶点V=｛0,1,2,…，n-1｝，T是构造生成树过程中已被考虑在生成树上的边的集合。Eij为顶点i、j之间的边，且i∈U，j∈V-U。

初始时，U只包含1个出发顶点i，T为空。从出发顶点i开始查找，连接该顶点的所有边中，如果边Eij具有最小权值,那么最小生成树应包含Eij。把j加到U中，把Eij加到T中，然后又从i、j开始，查找除去边Eij以外的连接i、j的最小代价边，依次重复上述过程，并使T不产生回路，直到U=V为止。这时，T即为要求的最小代价生成树的边的集合。

普里姆算法的时间复杂度为O（n²），适合于稠密图（边数远远大于顶点数的图）。

（2）克鲁斯卡尔（Kruskal）算法

设T(V,ψ)为初始状态只有n个顶点而无边的森林，顶点V=｛0,1,2,…，n-1｝，Eij为顶点i、j之间的边。

初始时，T只包含n个顶点。按边代价递增的顺序，依次选择Eij并加入T，重复上述过程，并使T不产生回路，直到所有顶点均连接为止，此时T为最小生成树。

克鲁斯卡尔算法的时间复杂度为O(elog2e），较适合于稀疏图（边数远远小于顶点数的图）。

下面，分别运用两种算法对例题进行解析。

例：下图是某地区的通信线路图，假设其中标注的数字代表通信线路的长度（单位：千米），现在要求至少要架设多长的线路，才能保持6个城市的通信联通？

普里姆算法：

1.选择A为出发顶点，查找连接顶点A的顶点中权值最小的边。顶点A分别与顶点B、C、E、F连接，AB=300，AC=400，AE=300，AF=200，AF最小，选择AF加入，此时包含的顶点为A、F。如下图：

2.查找连接顶点A、F的顶点中权值最小的边。与A连接的顶点有B、C、E，与F连接的顶点只有E，AB=300，AC=400，AE=300，FE=400，AB=AE=300最小，选择AB或AE加入（这里选择AE加入），此时已包含的顶点有A、F、E。如下图：

3.如选择AE加入，查找与顶点A、F、E连接的顶点中权值最小的边。还剩顶点B、C、D未加入，A与B、C连接，E与B、C、D连接。此时AB=300，AC=400，EB=300，EC=400，ED=200，ED最小，选择ED加入。此时已包含的顶点为A、F、E、D。如下图：

4.查找与顶点A、F、E、D连接的顶点中权值最小的边。还剩顶点B、C未加入，A与B、C连接，E与B、C连接，D与C连接，AB=300，AC=400，EB=300，EC=400，DC=300，AB=EB=DC=300最小，选择其中一条加入（这里选择EB加入），此时已包含的顶点为A、F、E、D、B。如下图：

5.查找与顶点A、F、E、D、B的顶点中权值最小的边。还剩顶点C未加入，C分别与A、B、D、E连接，CA=400，CB=400，CE=400，CD=300，CD最小，选择CD加入。至此，图中所有的顶点已加入完毕。

最小生成树已形成，如下图：

最小权值=AF+AE+ED+EB+CD

=AF+AB+AE+ED+CD

=AF+AB+EB+ED+CD

=1300

由此可见，图的最小生成树可能有多棵。如上述第2步开始，选择AB加入，此后选择EB（此时去掉了AE）加入，则最小生成树如下图：

如上述第2步开始，先选择AE加入后，再选择AB（此时去掉了EB）加入，则最小生成树如下图：

克鲁斯卡尔算法：

1.按照顶点之间边代价递增的顺序，对边从小到大进行排列。AF=ED=200＜AB=AE=EB=CD=300＜AC=BC=FE=CE=400。去掉图的所有边，只保留顶点，如下图：

2.选择AF加入，如下图：

3.选择ED加入。如下图：

4.选择AB加入。如下图：

5.选择CD加入。如下图：

6.选择EB加入。此时，最小生成树形成，如下图：