prim算法(prim与kruskal的结果一样吗)

摘要

生成树是图的一种表示。它有一个简单的规则，即边数等于顶点数减一。在加权图中寻找最小生成树在许多情况下都有应用。本文主要介绍一种求最小生成树的方法，即Prim。还有一种，下次继续。

生成树也叫生成树。在连通图中，它的最小连通子图是生成树。最小连通子图包含了一个连通图中的所有N个顶点，并且只有n-1条连通边(这里我们讨论的是无向图)。如下图所示的连接图:

它的最小连通子图可以有以下三种(其实还可以有其他几种):

看最小连通子图，可以得出图中顶点和边的关系是，边=顶点-1。

最小生成树

最小生成树也可以称为最小重量生成树或最小生成树，即所有生成树中总重量最小的树。既然提到了权，那么最小生成树就是一个带权的连通图(无向图仍在讨论)。如下图所示，右边部分是最小生成树:

制作一个最小生成树应用场景。如果要在城市之间铺设光缆，可以互通。铺设光缆的成本比较高，城市之间的距离也不一样，导致不同城市之间铺设光缆的成本也不一样。如何以最低的成本铺设光缆？最小生成树是解决方案。

有一点需要注意的是，在一个图中，每条边的权重是互不相同的，所以只会有一棵最小生成树，否则可能会有多棵最小生成树。

目前求最小生成树的经典算法有两种，分别是Prim (prim算法)和Kruskal (Kruskal算法)。

Prim 算法

在学习Prim算法之前，你需要知道分割定理，这是Prim定理的核心运算。

分割就是把图中的节点分成两部分，称为一个分割，如下图所示:

这里，把图切成两部分，顶点A、B、C是一部分，D、E是一部分。红色的边称为横切边，即一条边的两个顶点属于分割的两个部分，所以这条边称为横切边，如图BD，BE和CE。

分割定理意味着给定任何分割，横切边中权重最小的边一定属于最小生成树。

执行Prim算法时，假设一个带权(无向)的连通图是G(包括顶点和边)，A是G中的最小生成树，那么定义一个存储顶点的集合S。起始S中的顶点比G中的顶点小得多。然后，执行分割操作(后面会提到),直到S和G中的顶点数相同。

分割的操作是先找到分割C = (S，V-S)的最小横切边并合并到A中，同时将其顶点合并到集合S中，重复这个操作。如下图所示(从左到右，从上到下，注意图中的几个元素，绿顶点，蓝顶点，黑边，绿边，红边，虚分割线，权重):

在图中，分割从顶点B开始，红色的边是横切边，绿色的顶点是最小生成树集。以下是一些核心操作:

绿色顶点与蓝色顶点相连的边就是横切边，也是每次切分的部分；横切边中选择权值最小的，划分到绿色部分（最小生成树），然后将该边设置为绿色，权值相等，就随便选择一条边；当全部顶点都是绿色时，查看图中还是黑色的边，删除它，一个最小生成树就完成了。

先码，再把码梳理一遍:

设置& ltEdgeInfo & ltv，E & gt& gtprim() {迭代器& lt顶点& ltv，E & gt& gtit = vertices.values()。迭代器()；如果(！it.hasNext())返回null顶点& ltv，E & gtvertex = it . next()；设置& ltEdgeInfo & ltv，E & gt& gtedgeInfos = new HashSet & lt& gt();设置& lt顶点& ltv，E & gt& gtaddedVertices = new HashSet & lt& gt();addedvertices . add(vertex)；MinHeap & ltEdge & ltv，E & gt& gtheap = new MinHeap & lt& gt(vertex.outEdges，edge comparator)；int verticesSize = vertices . size()；而(！heap . isempty()& & added vertices . size()& lt；verticesSize){ Edge & lt；v，E & gtedge = heap . remove()；if(addedvertices . contains(edge . to))继续；edge infos . add(edge . info())；added vertices . add(edge . to)；heap . addall(edge . to . out edges)；}返回edgeInfos}prim函数返回一组EdgeInfo类型，主要存储起始顶点、终止顶点和权重:

公共静态类EdgeInfo & ltv，E & gt{私V from私V到；私E重；public EdgeInfo(V from，V to，E weight){ this . from = from；this.to = tothis.weight =重量；}prim函数中的前三行代码是为了确定图集中是否有顶点，并得到第一个顶点。这里，迭代器用于处理它(其他方法也是可能的):

迭代器& lt顶点& ltv，E & gt& gtit = vertices.values()。迭代器()；如果(！it.hasNext())返回null顶点& ltv，E & gtvertex = it . next()；接下来，我们创建一组addedVertices来存储Edgeinfo和最小生成树的顶点，存储第一个顶点，为后续的分割操作做准备。

这里，MinHeap用于存储放置在添加的城市中的顶点的外出边。MinHeap是一个小顶堆，它会把权重最小的边按照权重放在一个位置，后面添加的边会及时更新，权重最小的边排在最前面(如果对小顶堆感兴趣可以参考文章《数据结构与算法-基础(19)堆》)。

MinHeap & ltEdge & ltv，E & gt& gtheap = new MinHeap & lt& gt(vertex.outEdges，edge comparator)；最后不断取出堆中权重最小的边，放入Edgeinfo集合，将边的末端顶点放入addedVertices，再将末端顶点的边放入堆中。如果此边的结束顶点已经在addedVertices中，则不要执行前面的操作。直到添加的顶点数与图中的顶点数相同。

还有一种情况是heap中的元素没有了，也是这个时候结束。关于代码的最后一部分，请参见上面的第一部分。

总结生成树也被称为支撑树，图中的边数量等于顶点数量减一就可以被称为生成树，一个图中的生成树有很多；最小生成树是权值最小总和最小的生成树，在权值互不相同的图中，最小生成树只有一个；Prim 是求最小生成树的算法，它使用切分的方式处理，其中用到小顶堆的数据结构。