热门标签 | 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}










推荐阅读
  • 编译原理中的语法分析方法探讨
    本文探讨了在编译原理课程中遇到的复杂文法问题,特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略,包括递归下降解析、运算符优先级解析等,并提供了相关示例。 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 题目描述:计算从起点到终点的最小能量消耗。如果下一个单元格的风向与当前单元格相同,则消耗为0,否则为1。共有8个可能的方向。 ... [详细]
  • 入门指南:使用FastRPC技术连接Qualcomm Hexagon DSP
    本文旨在为初学者提供关于如何使用FastRPC技术连接Qualcomm Hexagon DSP的基础知识。FastRPC技术允许开发者在本地客户端实现远程调用,从而简化Hexagon DSP的开发和调试过程。 ... [详细]
  • linux网络子系统分析(二)—— 协议栈分层框架的建立
    目录一、综述二、INET的初始化2.1INET接口注册2.2抽象实体的建立2.3代码细节分析2.3.1socket参数三、其他协议3.1PF_PACKET3.2P ... [详细]
  • 本文详细介绍了如何在循环双链表的指定位置插入新元素的方法,包括必要的步骤和代码示例。 ... [详细]
  • 实现系统调用
    实现系统调用一、实验环境​本次操作还是基于上次编译Linux0.11内核的实验环境进行操作。环境如下:二、实验目标​通过对上述实验原理的认识,相信 ... [详细]
  • 本文探讨了如何高效地计算数组中和为2的幂的偶对数量,提供了从基础到优化的方法。 ... [详细]
  • UVa 1579 - 套娃问题
    本题主要涉及动态规划(DP)的应用,通过计算将前i个套娃合并成多个套娃组所需的最小操作次数来解决问题。具体来说,f(i) 表示前i个套娃合并成多个套娃组所需的操作次数,其计算公式为 f(i) = min(f(j) + dp(j+1, i))。 ... [详细]
  • 电商高并发解决方案详解
    本文以京东为例,详细探讨了电商中常见的高并发解决方案,包括多级缓存和Nginx限流技术,旨在帮助读者更好地理解和应用这些技术。 ... [详细]
  • RTThread线程间通信
    线程中通信在裸机编程中,经常会使用全局变量进行功能间的通信,如某些功能可能由于一些操作而改变全局变量的值,另一个功能对此全局变量进行读取& ... [详细]
  • Go从入门到精通系列视频之go编程语言密码学哈希算法(二) ... [详细]
  • 本文介绍如何手动实现一个字符串连接函数,该函数不依赖于C语言的标准字符串处理函数,如strcpy或strcat。函数原型为void concatenate(char *dest, char *src),其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]
  • 深入解析Python进程间通信:Queue与Pipe的应用
    本文详细探讨了Python中进程间通信的两种常用方法——Queue和Pipe,并通过具体示例介绍了它们的基本概念、使用方法及注意事项。 ... [详细]
  • 本文详细介绍了Sleep函数的基本概念、使用方法及其背后的实现原理。适合对Sleep函数的使用和实现感兴趣的开发者阅读。通过本文,您将了解如何在不同操作系统中使用Sleep函数,以及其在多线程编程中的重要性。 ... [详细]
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社区 版权所有