引入

在之前的学习中，我们已经介绍了图的储存方式等相关内容。

（这里待补坑）

数据结构课本上引入：

“假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑 这样一个问题，如何在最节省经费的前提下建立这个通信网”

在含有n个结点的连通网中挑选n-1条边构造一颗边权和最小（耗费最小），这个问题就是最小代价生成树（ Minimum Cost Spanning Tree）（简称最小生成树）构造问题。

定义补充

关于图的几个概念定义：

连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。

强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。

连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。

生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

算法

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：

MST性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边， 其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树

性质证明：

反证法：假设网N的任何一棵最小生成树都不包含（u，v）。设T是连通网上的一棵最小生成树， 当将边（u，v）加入到T中时，由生成树的定义，T中必存在一条包含（u，v)的回路。另一方面，由于T是生成树， 则在T上必存在另一条边（u’，v’），其中u’∈U，v’∈V - U，且u和u’之间，v和v’之间均有路径相通。 删去边（u’，v’），便可消除上述回路，同时得到另一棵生成树T’。因为（u，v）的代价不高于（u’，v’）， 则T’的代价亦不高于T，T’是包含（u，v）的一棵最小生成树，和假设矛盾。

下面就介绍两种使用MST性质生成最小生成树的算法：普里姆算法（Prim）和克鲁斯卡尔（Kruskal）算法。

2、普里姆算法—Prim算法

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