最小生成树（还没写完）

Myth丶恋晨 2022-10-28 10:13 131阅读 0赞

# 最小生成树 #

目标：在网络（带权图）的多个生成树中（生成森林），寻找一个各边权值之和最小的生成树。

首先明确：

*  使用不同的遍历图的方法，可以得到不同的生成树（广度与深度）；从不同的顶点出发，也可能得到不同的生成树。
 *  按照生成树的定义，n个顶点的连通网络的生成树肯定有n个顶点和仅仅n-1条边

构造最小生成树的准则：

*  必须只使用该网络中的边来构造最小生成树
 *  必须使用且仅使用n-1条边来联结网络中的n个顶点
 *  不能使用产生回路的边

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

建立数学模型：

顶点————表示城市，有n个；  
边————表示线路，有n-1条；  
边的权值————表示线路的经济代价；  
连通网————表示n个城市间的通信网。

问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的**代价之和最小**。此树便称为**最小生成树MST**

设想一下：先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到的很可能就是最小生成树！

求MST有多种算法，但最常用的是以下两种：

*  Kruskal（克鲁斯卡尔）算法
 *  Prim（普里姆）算法

Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。  
Prime算法特点: 将顶点归并，与边数无关，适于稠密网。

Prime算法：

假设N = (V,\{E\})是连通网,TE是N上最小生成树中边的集合。算法从U = \{u0\}(u0∈V),TE = \{\}开始,重复执行下述操作:在所有u∈U,v∈V-U的边(u,v) ∈E中找一条代价最小的边(u0, v0)并入集合TE,同时v0并入U,直至U = V为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/f20c6e9b15fa4909afeb6641746df681.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/28138b6cebf047028d23acd5c1095a6a.png