3. 最小生成树算法

"图的基本概念"中，我们总结了无向图之连通图，有向图之强连通图概念，下面补充一些概念

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

最小生成树集合表示

在一给定的无向连通图G = (V, E)中，(u, v) 代表连接顶点 u 与顶点v 的边，w(u, v) 代表此边的权重；若存在 T 为 E 的子集，G' = (V , T)构成的图为G的生成树，使得的 ∑w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。

大白话：

在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，考虑如何在成本最低的情况下建立这个通信网？
于是可以引入连通图来解决上述问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是搭建这条线路所需要的成本，所以现在有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

连通图&最小生成树

---

构造最小生成树算法大多采用了以下性质：

G＝ （V，E）为一个带权连通无向图，U是顶点集V的一个非空子集，若（u，v）是一条具有最小权的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。

---

两种最常见的最小生成树算法 --- 求带权连通无向图G＝ （V，E）的最小生成树G'

1. Prim算法（普里姆算法）

算法过程： 带权连通无向图G＝ （V，E）

1. 初始化 顶点集 V' = {u0}，u0为图G中任一顶点，边集 E' = ∅
V - V' = {... ...}，E
2. {（u , v）| u∈V'，v∈V - V'}，（u，v）∈E 且 （u，v）权值最小，将 v 加入到V' 中，（u，v） 加到 E'中
3. 循环步骤2，直至 V' = V

---

图解：

Prime算法

图解过程描述：
首先从图G的任一顶点a开始，将a加入V'集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-V'）中，我们也把b加入到集合V'中，并且输出边（a，b）的信息，这样我们的集合V'就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-V'）中，我们把c加入到集合V'中，并且输出对应的那条边的信息，这样我们的集合V就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合V'。

总结：不断加点的过程，称之为 加点法

代码实现

Code

---

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

算法过程： 带权连通无向图G＝ （V，E），Kruskal是按权值递增顺序选择合适的边来构造最小生成树的方法

1. 初始化 ： V'=V ， E'= ∅，T此时是一个仅含有|V|个顶点的森林（即初始化的T是图G将所有的边去掉构成的森林）
2. 循环 ：按图G的边的权值递增顺序，依次从 E-E' 中选择一条边加入到 T 中，保证这条边加入T 中不会构成回路，将这条边加入E'中，否则丢弃。循环，直到E'中含有一条n-1条边（即T构成为一棵树）

---

图解：仍以上图的连通网为例

Kruskal算法

图解过程描述：
（1）将图中的所有边都去掉（边集E'为空）。
（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环
（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。

总结：不断加边的过程，称之为 加边法

代码实现

Code

---

---

关键字：

最小生成树
Prim算法
Kruskal算法