首页 > 其他分享 >Boruvka求最小生成树

Boruvka求最小生成树

时间:2024-06-14 19:59:51浏览次数:38  
标签:连通 复杂度 最小 生成 Boruvka minw

写在前面

这是我学这个算法的时候看的博客:推荐博客(除了这个还看了老师发的资料)

为了复习以及加深理解,来简单写一篇学习笔记(预计半小时写完)

关于Boruvka

起因是在模拟赛遇到的T3。大意是:对于给出的完全图,\(w_{(u,v)}=a_{\max{(u,v)}}-a_{\min{(u,v)}}\),求最小生成树。
烧烤了半场比赛依然只拿了25分……
题解:用Boruvka算法简单解决。

当然这是一个最小生成树算法,那道题也是很显然的最小生成树题。

说到生成树,最先想到的就是Kruskal;然后是Prim(然而我Prim没怎么写过);至于Boruvka,大概是印象中只记得名字的存在。

简单来说,Boruvka像是前两者的结合体。它使用了Kruskal的贪心思想,同时也加入了Prim的向外扩展。

实现思路

最初令每个点为一个连通块,每一轮,对于所有连通块,求它连向其他连通块的最短边;如果一个连通块的最短边连向另一连通块,则把最小边加入图中。

伪代码

while 所有点未连通{
  for 连通块 i
    minw[i] = 从i连向其他连通块的最短边
  for 连通块 i
    if minw[i] 连接不同连通块{
      ans += minw[i].w;
      merge(minw[i].u, minw[i].v);
      连通块数量 -= 1;
    }
}

时间复杂度

假设求minw[i]的时间复杂度为\(T\),那么总的时间复杂度就是\(O(T\log_{2}N)\)。

解题

一般来说,运用Boruvka解题的关键就在于优化\(T\)

例如题中给出边权特殊的完全图
朴素的\(T\)即\(N^2\);针对边权进行优化使得\(T\)在\(N\log_{2}N\)左右

例题

经典模板-Xor-MST

0609校内模拟赛T3-最小生成树

写在后面

于是一个小时才写完。今天心态有点炸裂TT

标签:连通,复杂度,最小,生成,Boruvka,minw
From: https://www.cnblogs.com/meteor2008/p/18248497

相关文章

  • 编写一个.sh的脚本,然后通过 shell 脚本执行 Makefile 文件并把生成的可执行文件下载到
    要编写一个shell脚本来执行Makefile并下载生成的可执行文件到开发板,你需要确保开发板可以通过某种方式(如SSH、FTP、SCP等)访问。以下是一个简单的shell脚本示例,它使用scp命令将可执行文件从本地机器复制到开发板。假设你的开发板可以通过SSH访问,并且你已经配置了SSH密钥认证,这样你......
  • MATLAB偏最小二乘回归(PLSR)和主成分回归(PCR)分析光谱数据|附代码数据
    全文链接:http://tecdat.cn/?p=2655最近我们被客户要求撰写关于偏最小二乘回归(PLSR)和主成分回归(PCR)的研究报告,包括一些图形和统计输出。此示例显示如何在matlab中应用偏最小二乘回归(PLSR)和主成分回归(PCR),并讨论这两种方法的有效性当存在大量预测变量时,PLSR和PCR都是对因变量建模......
  • SSH实践生成密码
    $ssh-keygen-trsa-P''-f~/.ssh/id_rsa$cat~/.ssh/id_rsa.pub>>~/.ssh/authorized_keys$chmod0600~/.ssh/authorized_keys-t:指定生成密钥类型(rsa、dsa、ecdsa等)-P:指定passphrase,用于确保私钥的安全-f:指定存放密钥的文件(公钥文件默认和私钥同目录下,不同的是,存......
  • 探索生成式AI的未来:Chat与Agent的较量与融合
    近年来,生成式人工智能(AI)不仅在技术界引起了广泛关注,更成为了推动多个行业革新的关键力量。这种技术之所以备受瞩目,不仅在于其独特的创造性和高效性,还在于它对未来商业模式和社会结构可能产生的深远影响。在这篇文章中,我们将全面介绍生成式AI的概念、定义、应用以及潜在风险,......
  • 免费视频编辑神器 Tailor:智能裁剪、生成与优化!
    TailorTailor是令人惊叹的视频编辑神器!其人脸和语音剪辑精准无比,人脸识别能锁定人物画面,语音捕捉和裁剪独具魅力。视频生成方面,口播生成赋予图像灵魂,字幕生成准确契合,色彩生成让黑白鲜活,音频生成创造无限可能。优化上,背景更换如入奇幻世界,流畅度与清晰度也极佳。Tailor......
  • 使用腾讯元宝+markmap生成思维导图
    AI可以帮助我们进行提炼和总结,节省了大量搜索资料和查阅的时间,像上图这张思维导图,就是使用腾讯元宝大模型进行内容提炼,再使用markmap生成思维导图,下面讲解下详细实现步骤:一、工具准备腾讯元宝,腾讯出口的大语言模型,让他进行主题的提炼并生成我们想要的特定格式,访问地址:https://......
  • 用GAN网络生成彩票号码
    1.前言生成对抗网络(GAN,GenerativeAdversarialNetwork)是由IanGoodfellow等人在2014年提出的一种深度学习模型,用于学习和生成与真实数据分布相似的数据。GAN由生成器(Generator)和判别器(Discriminator)两个部分组成,通过相互对抗的方式进行训练。生成器接受随机噪声并生成假......
  • 讯飞有一个可以根据描述文本自动生成PPT的AI接口,有趣
    文档:https://www.xfyun.cn/doc/spark/PPTGeneration.html 价格方面提供了免费1000点的额度,生成一次是10点,正好100次,如果要购买的话最低要购买1344元的,没有按量付费的模式,个人小开发者可买不起。 让我们跑起来玩玩,官方提供了python的sdk,下载到本地: 不想下载sdk的,我......
  • AI时代的创新工具:如何利用AI生成独具个性的XMind思维导图?
    哈喽,大家好,我是木头左,物联网搬砖工一名,致力于为大家淘出更多好用的AI工具!背景随着互联网的发展,越来越多的人开始使用Markdown来编写文档。Markdown是一种轻量级的标记语言,它允许人们使用简单的文本格式来编写文档,然后将其转换为HTML、PDF等格式。而思维导图则是一种可视化的工......
  • 视频生成模型 Dream Machine 开放试用;微软将停止 Copilot GPTs丨 RTE 开发者日报 Vol.
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编......