带你理解最小生成树的生成

最小生成树

介绍 Prim算法简述Kruskal算法简述应用 知识点习题：

---

介绍

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树（Minimum Spanning Tree,MST）可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

关于图的几个概念定义：

连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

Prim算法简述

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

把图中的所有边按代价从小到大排序；把图中的n个顶点看成独立的n棵树组成的森林；按权值从小到大选择边，所选的边连接的两个顶点(ui,vi)，(ui,vi) 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

Kruskal算法简述

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息：

struct { char vertexData //表示u中顶点信息 UINT lowestcost //最小代价 }closedge[vexCounts]

应用

生成树和最小生成树有许多重要的应用。

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

知识点习题：

(a, b, c) 表示 ab 两点之间距离为c，求树(a, c, 3)，(b, d, 1)，(b, f, 5)，(d, c, 6)，(d, f, 5)，(e, f, 2)，(a, b, 12)，(a, e, 13) prim最小生成树边和为（ ）

A. 19 B. 17 C. 18 D. 20

正确答案： B

答案解析：

a ~ c ~ d ~ b ~ f ~ e : 3 + 6 + 1 + 5 + 2 = 17