算法与数据结构学习——最小生成树

引入

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

(这里待补坑)

数据结构课本上引入:

“假设要在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。