prim算法详解（prim算法adjvex）



普里姆算法（Prim算法），图论中的一种算法，可在加权连通图（即“带权连通图”）里搜索最小生成树。该算法的结果是一棵树。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

生成树：包含图G中的所有顶点；任意两个顶点有唯一路径。
最小生成树：是生成树；在所有生成树中，各边的权值之和最小的那棵。

实际意义：从图G的整体来看，求得连接各个顶点所需的最小代价。例如：有n个城市，在这n个城市间修建高速公路有多种不同的方案（不同的距离）。怎样修（哪个方案）是最省距离的。

（注：N个顶点的图中，其最小生成树的边为N-1条，且各边之和最小。树的每一个节点（除根节点）有且只有一个前驱，所以，只有N-1条边。）

假设G=(V, {E})是连通网（网：带权图），TE是图G的最小生成树T的边（Edge）集合。V是图G的顶点的集合，E是图G的边的集合。算法从U={u₀} (u₀∈V)，TE={}开始。重复执行下述操作：

• 在所有u∈U，v∈V-U的边(u, v)∈E中找一条代价（权值）最小的边(u₀, v₀)并入集合TE。
• 同时v₀并入U
• 直至U=V为止。此时TE中必有n-1条边，则T=(V, {TE})为N的最小生成树。

由算法代码（见下文）中的循环嵌套可得知此算法的时间复杂度为O(n²)。

• 在集合E中选取权值最小的边(u, v)，u∈U，v∈V且v∉U。（如果存在多条满足前述条件，即权值相同的边，则可任意选取其中之一。）
• 将v并入U，将(u, v)边加入TE。
  输出：用集合U和TE来描述所得到的最小生成树T。
  
  

解释：adjVex[3]==0，表示(v₀, v₃)，adjVex[5] == 0，表示(v₀, v₅)。lowCost[3] == ∞且adjVex[3] == 0，表示(v₀, v₃)边不存在；lowCost[5] == 11且adjVex[5] == 0，表示(v₀, v₅)边的权值为11。

如：邻接矩阵中的v₀行，v₀顶点与各顶点构成的边及其权值用下面这的方式表示：

示例一

(v₀, v₀, 0), (v₀, v₃, ∞), (v₀, v₅, 11)

在lowCost数组中0表示以该顶点为终点的边e已经并入图G的最小生成树T的边集合——TE集合，不需要再比较（搜索）由集合U中的顶点构成的各边的权值。而∞表示以该顶点为终点的边e不存在。

③操作：

1.上面示例一中，最小的权值为10，此时lowCost中下标k = 1，相应地adjVex[k]即adjVex[1] == 0，记录下此时的边为(v₀, v₁)。
2. 将adjVex[k]即adjVex[1]设为1，表示将顶点v₁放入图G的最小生成树的顶点集合U中。
3.将lowCost[k]即lowCost[1]设为0，表示：
①以v₁为终点的边已搜索。
②且相应地，令i = adjVex[k],则边(v_i, v_k)为最小生成树T中的一条边，放入TE（或此处程序中的直接输出）。
③将顶点v₁放入集合U中（lowCost[1]中的值不会再发生变化）。

4.然后，将焦点转向顶点v₁，看看从v₁开始的边有哪些是权值小于从之前的顶点v₀开始的边的。此时k == 1。则有以下过程：

由于lowCost[0]和lowCost[1]为0，所以从lowCost[2]开始比较权值。vex[1][2] == 18 < lowCost[2]，意思是(v₀, v₂)==∞不存在这条边，(v₁, v₂) == 18，存在权为18的边(v₁, v₂)，类似的还有vex[1][6] == 16 < lowCost[6]和vex[1][8] == 12 < lowCost[8]。
把k == 1赋值给
adjVex[2]、adjVex[6]和adjVex[8]。
把权值18、16和12赋值给
lowCost[2]、lowCost[6]和lowCost[8]。

更新后的权值数组和邻接顶点数组如下：

故下次循环从顶点v₁为起点去搜索lowCost中权值最小的边。如此往复循环，直到图G中的每一个顶点都被遍历到。（邻接矩阵的每一行都被遍历到）

④输出：

C#代码：直接看Prim2这个方法即可。

TypeScript代码

参考资料：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/20345.html