Prim(普里姆)算法求最小生成树的思想及C语言实例讲解_c语言普里姆算法资源-CSDN下载

版权申诉

普里姆算法

最小生成树

5星 · 超过95%的资源 163 浏览量 2020-12-25 17:41:46 上传评论 1 收藏 103KB PDF 举报

资源详情

资源评论

资源推荐

Prim(普里姆普里姆)算法求最小生成树的思想及算法求最小生成树的思想及C语言实例讲解语言实例讲解

Prim 算法思想：算法思想：

从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2，如此重复直到所有顶点均在所构

成树中为止。

最小生成树（MST）：权值最小的生成树。

生成树和最小生成树的应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使

其造价最小的生成树。

构造网的最小生成树必须解决下面两个问题：

1、尽可能选取权值小的边，但不能构成回路；

2、选取n－1条恰当的边以连通n个顶点；

MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－

U，则必存在一棵包含边(u,v)的最小生成树。

prim算法假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列

操作：

在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。

此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心:始终保持TE中的边集构成一棵生成树。

注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)

跟边的数目有关，适合稀疏图。

举个简单的例子来说明具体的实现方法：

G:图，用邻接矩阵表示

vcount:表示图的顶点个数

max_vertexes:图最大节点数

infinity:为无穷大

数组存储从0开始

由于最小生成树包含每个顶点，那么顶点的选中与否就可以直接用一个数组来标记used[max_vertexes];（我们这里直接使用

程序代码中的变量定义，这样也易于理解）；当选中一个数组的时候那么就标记，现在就有一个问题，怎么来选择最小权值

边，注意这里最小权值边是有限制的，边的一个顶点一定在已选顶点中，另一个顶点当然就是在未选顶点集合中了。我最初的

一个想法就是穷搜了，就是在一个集合中选择一个顶点，来查找到另一个集合中的最小值，这样虽然很易于理解，但是很明显

效率不是很高，在严蔚敏的《数据结构》上提供了一种比较好的方法来解决：设置两个辅助数组lowcost[max_vertexes]和

closeset[max_vertexes]，lowcost[max_vertexes]数组记录从U到V－U具有最小代价的边。对于每个顶点v∈V－

U,closedge[v], closeset[max_vertexes]记录了该边依附的在U中的顶点。

Prim 算法步骤：算法步骤：

T0 存放生成树的边，初值为空

输入加权图的带权邻接矩阵 C = (Cij)n×n (两点间无边相连则其大小为无穷)

为每个顶点 v 添加一属性 L(v) ：表 v 到 T0 的最小直接距离

（1) T0←∅, V1={v0}, C(T0)=0

（2) 对任意v ∈ V，L(v)←C(v, v0)

（3) If V==V1 then stop else goto next.

（4) 在 V-V1 中找点 u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},记 V1 中与 u 相邻点为 w.

（5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u}

（6) 对任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不变。

（7) Go to 3.

C++实现示例实现示例

prim.txt中的内容:

1 2 6

1 3 1

1 4 5

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论2

张小瑞学习笔记

2023-06-08

资源不错，内容挺好的，有一定的使用价值，值得借鉴，感谢分享。

内容反馈

版权申诉

weixin_38586279

粉丝: 2

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip