用c Prim算法实现最小生成树 一般情况下,假设n个顶点分成两个集合:U(包含已落在生成树上的结点)和 V-U(尚未落在生成树上的顶点),则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 输入图的相关信息,使用Prim算法,生成最小生成树(从图中序号最小的顶点开始)。 注意:选择邻接顶点时,若多个邻接顶点,按顶点编号从小到大的顺序,优先选择编号小的邻接顶点。 输入说明: 先输入图中顶点个数和边的数目,空格间隔; 然后输入每个顶点的数据; 最后依次输入每条边的起始和终止顶点的位序及边上的权值,格式为:顶点1位序 顶点2位序 权值。 输出说明: 按生成次序依次输出最小生成树中的各边的起始顶点位序和终止顶点位序,用英文逗号间隔,且用一对圆括号括起来。 注意:所有顶点的数据,不论是数字还是字符,顶点的位序按ASCII码值从小到大设置。 输入样例: 6 10 1 2 3 4 5 6 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 输出样例: (1,3) (3,6) (6,4) (3,2) (2,5)

时间: 2024-02-06 16:02:40 浏览: 23
以下是使用C++实现Prim算法求最小生成树的代码: ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 105; int n, m; int edge[MAXN][MAXN]; int vis[MAXN], dis[MAXN]; int prim() { int ans = 0; memset(vis, 0, sizeof(vis)); memset(dis, INF, sizeof(dis)); dis[1] = 0; for (int i = 1; i <= n; ++i) { int u = 0; for (int j = 1; j <= n; ++j) if (!vis[j] && (u == 0 || dis[j] < dis[u])) u = j; vis[u] = 1; ans += dis[u]; for (int v = 1; v <= n; ++v) if (!vis[v] && dis[v] > edge[u][v]) dis[v] = edge[u][v]; } return ans; } int main() { scanf("%d%d", &n, &m); memset(edge, INF, sizeof(edge)); for (int i = 1; i <= n; ++i) edge[i][i] = 0; for (int i = 1; i <= n; ++i) { char c; cin >> c; } while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); if (u == v) continue; edge[u][v] = edge[v][u] = min(edge[u][v], w); } for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]); for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (edge[i][j] != INF) printf("(%d,%d) ", i, j); return 0; } ``` 注意:以上代码实现了Prim算法求最小生成树,但是同时还加入了Floyd算法求任意两点之间最短路径的代码。如果只需要Prim算法求最小生成树,可以将最后的两重循环替换为Prim算法即可。

相关推荐

最新推荐

recommend-type

算法与数据结构实验三Prim最小生成树

用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
recommend-type

2024嵌入式大厂面经CVTE

2024嵌入式大厂面经CVTE提取方式是百度网盘分享地址
recommend-type

掺工业废钛石膏制备自密实混凝土研究

虽然自密实混凝土作为目前建筑领域应用最广泛的材料,但是由于其性能等方面的局限性,导致了目前普通自密实混凝土难以满足不断提高的工程建设要求。研究发现, 通过在自密实混凝土中添加钛石膏等可以验证混凝土各方面性能的提高。且向自密实混凝土中添加工业废钛石膏,将其应用于建材领域,不仅可以解决目前市场上对自密实混凝土的运用问题,还能改善环境及固体废弃物综合利用的问题。因此开展对掺工业废钛石膏制备自密实混凝土的研究。 在本文中,我们对掺工业废钛石膏制备自密实混凝土静力学性能做了系统性试验,对于掺工业废钛石膏制备自密实混凝土中钛石膏质量份数,我们采用的是 85 份、90 份和 95 份。整个试验可分为两个部分:一、单轴压缩试验和巴西圆盘劈裂抗拉试验,通过这两个试验主要得出钛石膏自密实混凝土的抗压强度、弹性模量与劈裂抗拉强度;二、不同粉料配比对掺工业废钛石膏制备自密实混凝土的影响,通过对不同粉料制成的掺工业废钛石膏制备自密实混凝土的坍落扩展度和离析率影响试验。最后分析试验数据,从而得出本文结论。 本文通过对大量试验数据的总结与分析,结合国内外相关研究的已有结论, 总结出当工业废钛石膏质量份数增加到
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB正态分布协方差分析:揭示正态分布变量之间的协方差

![MATLAB正态分布协方差分析:揭示正态分布变量之间的协方差](https://site.cdn.mengte.online/official/2021/11/20211128213137293.png) # 1. 正态分布概述 正态分布,又称高斯分布,是统计学中最重要的连续概率分布之一。它广泛应用于自然科学、社会科学和工程领域。 正态分布的概率密度函数为: ``` f(x) = (1 / (σ√(2π))) * exp(-(x - μ)² / (2σ²)) ``` 其中: - μ:正态分布的均值 - σ:正态分布的标准差 - π:圆周率 正态分布具有以下特性: - 对称性:
recommend-type

我正在开发一款个人碳足迹计算app,如何撰写其需求分析文档,请给我一个范例

为了更全面、清晰地定义个人碳足迹计算app的需求,需求分析文档应该包含以下内容: 1.项目简介:对该app项目的概述及目标进行说明。 2.用户分析:包括目标用户群、用户需求、行为等。 3.功能需求:对app的基本功能进行定义,如用户登录、数据录入、数据统计等。 4.非功能需求:对使用app的性能和质量等进行定义,如界面设计、数据安全、可扩展性等。 5.运行环境:包括app的开发环境和使用环境。 下面是一个范例: 需求分析文档 1. 项目简介 该app项目旨在为用户提供一款方便、易用、可定制的个人碳足迹计算平台,以促进环保和可持续性发展。 2. 用户分析 目标用户群:全球关
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。
recommend-type

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依
recommend-type

MATLAB正态分布相关性分析:探索正态分布变量之间的关联

![MATLAB正态分布相关性分析:探索正态分布变量之间的关联](https://img-blog.csdnimg.cn/bd5a45b8a6e94357b7af2409fa3131ab.png) # 1. MATLAB中正态分布的理论基础 正态分布,又称高斯分布,是一种常见的概率分布,其概率密度函数为: ``` f(x) = (1 / (σ√(2π))) * e^(-(x-μ)² / (2σ²)) ``` 其中,μ表示正态分布的均值,σ表示标准差。正态分布具有以下特点: - **对称性:**正态分布的概率密度函数关于均值μ对称。 - **钟形曲线:**正态分布的概率密度函数呈钟形曲线