热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Prim算法优化实现:基于优先队列的最小生成树构建方法

Prim算法在处理稠密图时表现出色,尤其适用于边数远多于顶点数的情形。传统实现的时间复杂度为\(O(n^2)\),但通过引入优先队列进行优化,可以在点数为\(m\)、边数为\(n\)的情况下显著降低时间复杂度,提高算法效率。这种优化方法不仅能够加速最小生成树的构建过程,还能在大规模数据集上保持良好的性能表现。

    prim算法适合稠密图,即边数较多而点较少的情况,时间复杂度为n^2,堆优化的情况下,如果点数为m,边数为n,可以达到nlongm,我还是习惯用优先队列写这个算法,思想很简单,就是每次寻找一条由已加入集合的点和与它们相邻的没加入集合的点的权值最小边(有点绕理解下),进行n-1次就找出来了,也是贪心的思想,实现就是随便找一个初始节点,然后建一个最小堆(边小的先pop出来),把该节点的vis值置为1,遍历该节点相邻的节点,如果没有被vis标记过,就加入边到堆中,扫完了以后处理堆中数据,如果弹出的边被标记过就pop,没有就取出来,把边通往的节点置为key,下次就加入key节点有关没有标记过的边。。一直循环,由于最小生成树边数与节点的关系为m=n-1,所以要循环n-1次,把每一次堆弹出边的值累加起来就是最小生成树的值了

下面是例题:


1943: 最优布线问题

Time Limit: 1 Sec  Memory Limit: 128 MB  64bit IO Format: %lld
Submitted: 19  Accepted: 10
[Submit][Status][Web Board]

Description


学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。
当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。
现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。


Input


多组测试数据。
第一行为整数n&#xff08;2<&#61;n<&#61;100&#xff09;&#xff0c;表示计算机的数目。
此后的n行&#xff0c;每行n个整数。第x&#43;1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。


Output


输出一个整数&#xff0c;表示最小的连接费用。


Sample Input 


3
0 1 2
1 0 1
2 1 0








Sample Output


2





[Submit][Status][Web Board]


题解&#xff1a;

这题因为边数较多&#xff0c;最好用prim算法&#xff0c;然后下面代码里面有注释

代码&#xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct edge//保存边的情况&#xff0c;to为通往的边&#xff0c;不需要保存from
{int to;int v;friend bool operator<(const edge& x,const edge& y)//优先队列即最小堆{return x.v>y.v;}
};
priority_queueq;
int vis[105];//判断是否标记数组
int p[105][105];//存图
int n;
int main()
{int i,j,x,y,d2,d1,s,key;edge now;while(scanf("%d",&n)!&#61;EOF){for(i&#61;0;i}










推荐阅读
  • 在稀疏直接法视觉里程计中,通过优化特征点并采用基于光度误差最小化的灰度图像线性插值技术,提高了定位精度。该方法通过对空间点的非齐次和齐次表示进行处理,利用RGB-D传感器获取的3D坐标信息,在两帧图像之间实现精确匹配,有效减少了光度误差,提升了系统的鲁棒性和稳定性。 ... [详细]
  • 深入解析Gradle中的Project核心组件
    在Gradle构建系统中,`Project` 是一个核心组件,扮演着至关重要的角色。通过使用 `./gradlew projects` 命令,可以清晰地列出当前项目结构中包含的所有子项目,这有助于开发者更好地理解和管理复杂的多模块项目。此外,`Project` 对象还提供了丰富的配置选项和生命周期管理功能,使得构建过程更加灵活高效。 ... [详细]
  • Python与R语言在功能和应用场景上各有优势。尽管R语言在统计分析和数据可视化方面具有更强的专业性,但Python作为一种通用编程语言,适用于更广泛的领域,包括Web开发、自动化脚本和机器学习等。对于初学者而言,Python的学习曲线更为平缓,上手更加容易。此外,Python拥有庞大的社区支持和丰富的第三方库,使其在实际应用中更具灵活性和扩展性。 ... [详细]
  • PHP中元素的计量单位是什么? ... [详细]
  • 从零起步:使用IntelliJ IDEA搭建Spring Boot应用的详细指南
    从零起步:使用IntelliJ IDEA搭建Spring Boot应用的详细指南 ... [详细]
  • BZOJ4240 Gym 102082G:贪心算法与树状数组的综合应用
    BZOJ4240 Gym 102082G 题目 "有趣的家庭菜园" 结合了贪心算法和树状数组的应用,旨在解决在有限时间和内存限制下高效处理复杂数据结构的问题。通过巧妙地运用贪心策略和树状数组,该题目能够在 10 秒的时间限制和 256MB 的内存限制内,有效处理大量输入数据,实现高性能的解决方案。提交次数为 756 次,成功解决次数为 349 次,体现了该题目的挑战性和实际应用价值。 ... [详细]
  • 本文将详细介绍在Android应用中添加自定义返回按钮的方法,帮助开发者更好地理解和实现这一功能。通过具体的代码示例和步骤说明,本文旨在为初学者提供清晰的指导,确保他们在开发过程中能够顺利集成返回按钮,提升用户体验。 ... [详细]
  • 本项目在Java Maven框架下,利用POI库实现了Excel数据的高效导入与导出功能。通过优化数据处理流程,提升了数据操作的性能和稳定性。项目已发布至GitHub,当前最新版本为0.0.5。该项目不仅适用于小型应用,也可扩展用于大型企业级系统,提供了灵活的数据管理解决方案。GitHub地址:https://github.com/83945105/holygrail,Maven坐标:`com.github.83945105:holygrail:0.0.5`。 ... [详细]
  • 在Spring与Ibatis集成的环境中,通过Spring AOP配置事务管理至服务层。当在一个服务方法中引入自定义多线程时,发现事务管理功能失效。若不使用多线程,事务管理则能正常工作。本文深入分析了这一现象背后的潜在风险,并探讨了可能的解决方案,以确保事务一致性和线程安全。 ... [详细]
  • Spring框架入门指南:专为新手打造的详细学习笔记
    Spring框架是Java Web开发中广泛应用的轻量级应用框架,以其卓越的功能和出色的性能赢得了广大开发者的青睐。本文为初学者提供了详尽的学习指南,涵盖基础概念、核心组件及实际应用案例,帮助新手快速掌握Spring框架的核心技术与实践技巧。 ... [详细]
  • Spring Boot 实战(一):基础的CRUD操作详解
    在《Spring Boot 实战(一)》中,详细介绍了基础的CRUD操作,涵盖创建、读取、更新和删除等核心功能,适合初学者快速掌握Spring Boot框架的应用开发技巧。 ... [详细]
  • 本文详细解析了如何使用 jQuery 实现一个在浏览器地址栏运行的射击游戏。通过源代码分析,展示了关键的 JavaScript 技术和实现方法,并提供了在线演示链接供读者参考。此外,还介绍了如何在 Visual Studio Code 中进行开发和调试,为开发者提供了实用的技巧和建议。 ... [详细]
  • 本文深入探讨了 MXOTDLL.dll 在 C# 环境中的应用与优化策略。针对近期公司从某生物技术供应商采购的指纹识别设备,该设备提供的 DLL 文件是用 C 语言编写的。为了更好地集成到现有的 C# 系统中,我们对原生的 C 语言 DLL 进行了封装,并利用 C# 的互操作性功能实现了高效调用。此外,文章还详细分析了在实际应用中可能遇到的性能瓶颈,并提出了一系列优化措施,以确保系统的稳定性和高效运行。 ... [详细]
  • 本文详细探讨了C语言中`extern`关键字的简易编译方法,并深入解析了预编译、`static`和`extern`的综合应用。通过具体的代码示例,介绍了如何在不同的文件之间共享变量和函数声明,以及这些关键字在编译过程中的作用和影响。文章还讨论了预编译过程中宏定义的使用,为开发者提供了实用的编程技巧和最佳实践。 ... [详细]
  • 本文详细解析了 MySQL 5.7.20 版本中二进制日志(binlog)崩溃恢复机制的工作流程。假设使用 InnoDB 存储引擎,并且启用了 `sync_binlog=1` 配置,文章深入探讨了在系统崩溃后如何通过 binlog 进行数据恢复,确保数据的一致性和完整性。 ... [详细]
author-avatar
游泳
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有