什么是最小生成树以及如何构建

文章目录

一，概念回顾 - 生成树

1.1 什么是生成树
1.2 如何建立无向图的生成树

二，最小生成树（Minimum Spanning Trees）

2.1 最小生成树的典型用途
2.2 构造最小生成树（MST）

2.2.1 MST 性质
2.2.2 Prim 算法构建最小生成树
2.2.3 Kruskal 算法构建最小生成树
2.2.4 Prim 与 Kruskal 算法比较

预习：图的基本概念及图演算法

一，概念回顾 - 生成树

1.1 什么是生成树

生成树：所有顶均由边链接在一起，但不存在回路的图。

多一条边会出现回路
少一条边会出现链接不到的顶点
一个图可以有许多棵不同的生成树

所有生成树具有以下共同特点

生成树的顶点个数与图的顶点个数相同；
生成树是图的极小连通子图，去掉一条边则非连通；
一个有 n 个顶点的连通图的生成树有 n-1 条边；
在生成树中再加一条边必然形成回路；
生成树中任意两个顶点间的路径是唯一的。

注意含有 n 个顶点 n-1 条边的图不一定是生成树。
什么是最小生成树以及如何构建

1.2 如何建立无向图的生成树

回顾：深度 / 广度优先搜索
什么是最小生成树以及如何构建
设图 G = ( V, E ) 是个连通图，当从图任一顶点出发遍历图G 时，将边集 E(G) 分成两个集合 T(G) 和 B(G)。其中 T(G) 是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边的集合。显然，G1(V, T) 是图G 的最小连通子图。即子图G1 是连通图G 的生成树。

二，最小生成树（Minimum Spanning Trees）

如下图，生成了两个生成树，权值分别为 19 和 17.
什么是最小生成树以及如何构建
最小生成树

给定一个无向网络，则该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

2.1 最小生成树的典型用途

欲在 n 个城市间建立通信网，在 n 个城市应铺 n-1 条线路；
但因为每条线路都会相对应的经济成本，而 n 个城市最多有 n*(n-1)/2 条线路，那么，如何选择 n-1 条线路，使总费用最少？

什么是最小生成树以及如何构建
显然，此联通网是一个生成树，并且我们希望他是一个最小生成树。

2.2 构造最小生成树（MST）

2.2.1 MST 性质

视频讲解：6.6.1最小生成树3–MST性质
构造最小生成树的算法很多，其中多数算法都利用了MST的性质。

MST 性质

设 N =（ V, E ）是一个连通网，U 是顶点集 V 的一个非空子集。若边（u，v）是一条具有最小权值的边，其中 u∈U，v∈V - U，则必存在一棵包含边（u，v）的最小生成树。

什么是最小生成树以及如何构建
MST 性质解释：
再生成树的构造过程中，图中 n 个顶点分属两个集合

已经落在生成树上的顶点集：U
尚未落在生成树上的顶点集：V - U

接下来则应在所有连通 U 中顶点和 V - U中顶点的边中选取权值最小的边。
什么是最小生成树以及如何构建

2.2.2 Prim 算法构建最小生成树

视频讲解：青岛大学–王卓 Prim 算法
算法思想

设 N = （V，E）是连通图，TE 是 N 上最小生成树中边的集合。
初始令 U = { u₀ }，（u₀∈V），TE = { }。
在所有 u∈U，v∈V - U的边（u，v）∈E 中，找一条代价（权值）最小的边（u₀，v₀）。
如下图 U = { 1，3 }，V - U = { 2, 4, 5, 6 }

如下图 U = { 1，3 ，6}，V - U = { 2, 4, 5 }
将（u₀，v₀）并入集合 TE，同时 v₀ 并入 U。
重复上述操作直至 U = V 为止，则 T = ( V, TE ) 为 N 的最小生成树。
最终结果如下图所示