贪心算法实验(最小生成树) (2).docx
版权申诉
92 浏览量
2023-04-13
19:41:01
上传
评论
收藏 112KB DOCX 举报
算法分析与设计实验报告
第 一 次附加实验
姓名
时间
学号
地点
班级
12.12 上午
工训楼 309
贪心算法实验(最小生成树)
通过上机实验，要求掌握贪心算法的思想，利用 prim 算法求解最小生成树并
实现。
设 G=(V,E)是连通带权图，V={1,2,…,。n}构造 G 的最小生成树的 Prim 算法的基
本思想是：首先置S={1}，然后，只要S 是 V 的真子集，就作如下的贪心选择：
选取满足条件 iS，jV-S，且c[i][j]最小的边，将顶点j 添加到 S 中。这个过程
一直进行到 S=V 时为止。在这个过程中选取到的所有边恰好构成 G 的一棵最
小生成树。
（1）用邻接矩阵表示无向图，并进行初始化，同时选择源点放在集合s 中；
（2）选取候选集中距离最短的顶点，把其加入终点集合中；
（3）以该顶点为新考虑的中间顶点，修改候选集中个顶点距离，若经过该点
后，各点到达源点距离比原来距离短，则修改距离；
（4）重复以上 2、3 步，直到所有候选集中都被加入到终点集中。
template<class Type>
//参数为结点个数n，和无向带权图中各结点之间的距离c[][N+1]
void Prim(int n,Type c[][N+1])
{
Type lowcost[N+1]; //记录c[j][closest]的最小权值
bool s[N+1]; //标记各结点是否已经放入集合s中
s[1]=true;
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
资源评论
คิดถึง643
- 粉丝: 3917
- 资源: 1万+
最新资源
- 基于Typescript和PHP的编程知识储备库设计源码 - study-php
- Screenshot_2024-05-28-11-40-58-177_com.tencent.mm.jpg
- 基于Dart的Flutter小提琴调音器APP设计源码 - violinhelper
- 基于JavaScript和CSS的随寻订购网页设计源码 - web-order
- 基于MATLAB的声纹识别系统设计源码 - VoiceprintRecognition
- 基于Java的微服务插件集合设计源码 - wsy-plugins
- 基于Vue和微信小程序的监理日志系统设计源码 - supervisionLog
- 基于Java和LCN分布式事务框架的设计源码 - tx-lcn
- 基于Java和JavaScript的茶叶评级管理系统设计源码 - tea
- IMG_5680.JPG
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
