最小生成树Prim算法的理解

╰半橙微兮° 2022-06-03 07:51 193阅读 0赞

## 一、 Prim算法构造过程的数学概念 ##

1，*原文引述*  
*任意给定带权图N = \{V, E\}，算法**始终将顶点集合分成不重叠的两部分**， V = V1 U （V - V1），也就是该图的一个割（cut）。**其中V1是生成树的顶点集合，（V - V1）是图中不在生成树内顶点的集合。**这里只考虑连通的网络（连通图），所以只要V1与（V-V1）均非空，**他们之间就至少有一条边相连**，称这种边为该割的一座桥（bridge）。每一轮迭代中都要在当前割的所有桥中，挑选出权值最小者（u，v），u属于V1，v属于（V-V1），然后将顶点v加入到生成树的顶点集合当中，即令V1 = V1 U \{v\}；将边（u，v）加入到生成树的边集合E1中，即E1 = E1 U（u，v）。（注意：若最短桥有多座，又该怎么处理？），这一过程不断重复，每经过一轮迭代，V1中都会增加一个顶点，E1中都会增加一条边。当V1中含有n个顶点，E1中含有n-1条边时，算法终止。此时(V1，E1)就给出N的一棵最小生成树。*

2，上面用离散数学中图的概念对Prim算法在理论上做了阐述，其实在对图的概念有了理解之后，上面的叙述还是十分明晰易懂的。最重要的就是上述定义中的黑体字部分：

> （1）顶点将始终将图分出两部分，即有两个不同但又互补的顶点集合——已经选入最小生成树中的点和未被选入的点。（点割集概念）  
> （2）因为是连通图，所以这两个点集之间一定至少有一条边将两个点集连通，这个边的一个端点属于V1另一个端点属于（V-V1）。（桥的概念）

3，Prim算法“取点”与“砍边”的过程  
![这里写图片描述][SouthEast]  
上面的每条不同颜色的线代表每次对V1与（V-V1）两个点集的重新划分，每条线的标号（1，2，3，4，5，6）表示先后顺序。  
1》第一个选入的点是0号，那么0号点与1，2，3，4，5，6号点就分属于两个集合V1和（V-V1），这也表明0号点已经是最小生成树中的点了。而第一条线（图中红色线）便把0号节点与1，2，3，4，5，6号节点分割开，这个时候红线经过了两条节之间的边（权值分别是10与28），其实这两条边就是两个点集之间的桥。我们希望最后的权值之和最小，当然就选择了权值为10（10 小于28）的边，这时候5号节点自然被选入进来。

2》上面这个过程结束后，0号节点与5号节点属于V1，而其他的仍属于（V-V1）。那么我们再画一条线（图中黄色线）将这两个点集合区分。这时黄线又经过了权值是28、25的桥，这次继续选最小的25，自然4号节点又被分割过来。

3》继续画线，继续分割，继续找权值较小的桥，……

4》最后所有的顶点都被选进最小生成树的顶点集当中，当然在割点的过程中我们也选择了一系列权值较小的边，这些边便构成了最小生成树的边集合。

5》下面是每用线分割一次所形成的点割集。  
![这里写图片描述][SouthEast 1]

## 二、Prim算法的实现 ##

1，*原文引述：与Kruskal算法类似，需要一个最小堆存储图的边，每次选出一个端点在生成树中，另一个端点不在生成树的权值最小的边（u，v），他正好在最小堆的堆顶，将其从堆中退出，加入生成树中。然后将新出现的所有一个端点在生成树中一个端点不在生成树的边都插入最小堆当中（自：就是划线线与选线的过程）。下一轮迭代中，下一条满足要求的权值最小的又上升到最小堆的堆顶。如此重复n-1次，最后建立其该图的最小生成树。*

2，有关的代码实现可以参考相应的教材《数据结构C++语言描述第二版》（殷人昆著），因为其涉及到最小堆代码、图的存储代码，所以代码比较长，不再贴出。

## 三、Kruskal算法与Prim算法的对比 ##

在实现两种算法的过程中可以感受到，Kruskal是在每次选最小的边（边割集），这样当一个图结构的节点很多、边较少的时候（稀疏图），使用Kruskal算法更加高效。而Prim算法是在分割图中的点（点割集），这样当一个图点较少、边很多的时候（稠密图），使用Prim算法更加高效。

推荐博文：[http://blog.chinaunix.net/uid-25324849-id-2182922.html][http_blog.chinaunix.net_uid-25324849-id-2182922.html]

[SouthEast]: /images/20220603/515b9c3bb74547bea5df3779deaa295c.png
[SouthEast 1]: /images/20220603/0764e042a7ff4e2f87d1a72b3706e4a7.png
[http_blog.chinaunix.net_uid-25324849-id-2182922.html]: http://blog.chinaunix.net/uid-25324849-id-2182922.html