没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
6页
在计算机科学中,普里姆(也称为Jarník's)算法是一种贪婪算法,它为加权的无向图找到一个最小生成树 。这意味着它找到边的一个子集,能够形成了一个包括所有顶点的树,其中在树中所有边的权重总和最小。该算法通过从任意起始顶点开始一次给树增加一个顶点来操作,在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。 该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后,后来在1957年被计算机科学家罗伯特·普里姆,以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此,它有时也被称为Jarník算法,普里姆-jarník算法, 普里姆-迪克斯特拉算法或者DJP算法。
资源推荐
资源详情
资源评论
1. 描述
在计算机科学中,普里姆(也称为Jarník's)算法是一种贪婪算法,它为加权的无向图找到一个最小生成树 。
这意味着它找到边的一个子集,能够形成了一个包括所有顶点的树,其中在树中所有边的权重总和最小。该
算法通过从任意起始顶点开始一次给树增加一个顶点来操作,在每个步骤中添加从树到另一个顶点的花费最
小的可能的连接。
该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后,后来在1957年被计算机科学家罗伯特·普里姆,以及
在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此,它有时也被称为Jarník算法,普里姆-jarník
算法,普里姆-迪克斯特拉算法或者DJP算法。
该算法可以非正式地描述为执行以下步骤:
1. 从图中任意选择一个顶点,然后用这个顶点初始化一颗树。
2. 把这棵树增加一条边:在满足能将树和不在树中的顶点连接起来的所有边中,找到而且具有最小的权重
的边,然后把这条边增加到树里面。
3. 重复步骤2(直到所有顶点都包含在树中)。
更详细地说,它可以按照下面的伪代码语句实现。
1. 在图中把每个顶点 v 都关联一个数C[v] (表示连接"v"的最小花费)和一条边E[v](有着最小花费的连接
的边)。要初始化这些值,首先将所有的C[v] 设为 +∞(或者任何比图中最大边权重更大的数值)以及
将每条边设为一个特殊的标记值,从而表示"v"和之前的顶点之间没有边连接。
2. 初始化一个空的森林"F"和未被包含进"F"的顶点的集合"Q"(初始状态下是所有的顶点)。
3. 重复下面的步骤直到Q为空为止:
1. 从 Q 中找到具有最小可能值C[v]的顶点"v"并将其从集合中移出
2. 将 v 加入到 F 中,如果E[v] 不是标记值,那么将 E[v] 也加入到 F中
3. 在边vw上进行循环,从而将v连接到其他的顶点w上。对于每条这样的边, 如果w仍然属于Q并且vw
的权重要比C[w]小, 那么执行以下步骤:
1. 将C[w] 设为边 vw的花费
2. 用 E[w] 来指向边 vw。
4. 返回 F
如上所述,算法的起始顶点将被任意选择,因为算法主循环的第一次迭代中在Q
中
将有一组顶点权重相等,
当算法将输入图的每个连接部分都构成生成树时,它会自动在F
中生成一颗新的树
。该算法可以通过设置C[s]
小于C的其他任何值(例如,为零)
,从而
修改为可以从任何特定顶点s开始,并且它可以修改为只找到一个
生成树,而不是整个生成森林(与非正式描述更加符合),方法是每当遇到标记为没有关联边的另一个顶点时
就停止。
算法的不同变体在集合Q的实现方式上互不相同:实现为简单的链表或顶点数组,或更复杂的优先队列数据
结构。这种选择导致算法的时间复杂度不同。一般来说,优先级队列会更快找到有着最小的花费的顶点v,但
当C[w]的值变化时更新的时间会很长。
资源评论
孤蓬&听雨
- 粉丝: 8560
- 资源: 364
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- keil2 + proteus + 8051.exe
- 1961ee27df03bd4595d28e24b00dde4e_744c805f7e4fb4d40fa3f695bfbab035_8(1).c
- mediapipe-0.9.0.1-cp37-cp37m-win-amd64.whl.zip
- windows注册表编辑工具
- mediapipe-0.9.0.1-cp37-cp37m-win-amd64.whl.zip
- 校园通行码预约管理系统20240522075502
- 车类型数据集6250张VOC+YOLO格式.zip
- The PyTorch implementation of STGCN.STGCN-main.zip
- 092300108.cpp
- 车类型数据集6000张VOC+YOLO格式.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功