最小生成树prim算法流程图(prim算法生成最小生成树)

最小生成树 假设你是电信的实施工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大致如图,其中V0~V8是村庄,之间连线代表可达距离,数字代表里程数。领导要求你用最小成本完成这次任务,如何做? 显然这是一个带权值的图,即是网结构。所谓最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并使得权值和最小。 定义 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一…

最小生成树

假设你是电信的实施工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大致如图,其中V0~V8是村庄,之间连线代表可达距离,数字代表里程数。领导要求你用最小成本完成这次任务,如何做?

最小生成树-普里姆(Prim)算法

显然这是一个带权值,即是网结构。所谓最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并使得权值和最小


定义

一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一个树的n-1条边——我们把构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)


我想在讲算法之前我们先做一下思考,我们如何找到该条路径?

  • 我们是否可以从某一点开始寻找呢?
  • 我们从哪一个地点作为起始点呢?
  • 我们找到第一个点以后如何找最小权值的边呢?

第一步
我想先从概念下手:
首先,因为一个连通图含有图中全部顶点,所以我们可以从任意顶点出发(开始寻找),最终结果应该是一致的。但是为了方便讲述我还是想从V0开始出发(此时我们站在V0)。

最小生成树-普里姆(Prim)算法

起始点找到了,那么如何找起始点到第一个顶点的边呢?

逆着想一下,与V0邻接有且仅有两条边(V0,V1),(V0,V5),我们必须要选一条(因为我们必须要到达V0),所以我们干脆在V0的两条边上选一条到达V0。

我们站在V0巡视了一下两条边,然后选择了(V0,V1)(此处有判断)。

最小生成树-普里姆(Prim)算法

然后我们记录一下V0我们已经走过,走过的路标记为红色。

第二步
但是接下来我们该如何走呢?
其实我也很迷茫,既然不知道,那就选当前能走的路的最近的一条吧。
现在我们有两种选择,第一种从V0出发,第二种从V1出发,分别产生的可能性如下(绿色):

最小生成树-普里姆(Prim)算法

选一条最短的

最小生成树-普里姆(Prim)算法

接下来看V5和V1能到达哪里?然后继续寻找…直到最后一个顶点被连通(从0-n的循环)
其实这就是普里姆算法的核心思路,既然思路知道了,我们对比算法来讲解吧。

普里姆(Prim)算法

在讲之前我们先选一种图的存储结构吧,这里我们用图的邻接矩阵存储结构来讲解。

最小生成树-普里姆(Prim)算法
  • 39-47行就是上面讲述的寻找我们当前顶点邻接的最小权值边,(用之前的例子讲:第一次循环是顶点V0所有的边,第二次循环除去边(V0,V1)以后顶点V0和V1所有的边,以此类推)
  • 而51-58行则是更新当前所有可能的边的最小权值。
  • 算法比较晦涩的是adjvex[MAXVEX]和lowcost[MAXVEX]的理解,一旦理解这两个数组的含义,这个算法也就没难点了。

由代码中的循环嵌套可得知此算法的时间复杂度为O(N^2)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022年5月13日 下午4:18
下一篇 2022年5月13日 下午4:19

相关推荐

  • 手机冲不进去电怎么回事,解决手机充不上电的小妙招

    感觉手机要没电了,手机电量10%才会提示低电量,电量50%的时我已经拿出充电器,乖乖充电了。但是,电没来!每个人心里都有一个数值,一旦手机电量跌破这个数值,我们的内心就会开始恐慌,电量危机,俨然成为我们生活中的一大问题。手机无法充电,像是一道晴天霹雳,把自己的心情雷的那是一个外焦里嫩,手机没电,更是让自己魂不守舍,造成诸多不便。什么原因会导致手机无法充电呢?今天秦小翼就带你一探究竟~~~ 1、运行…

    2022年7月25日
    800
  • 删除好友后怎么恢复聊天记录,详细操作方法请看本篇

    自打IOS11发布后,新功能就一直在被果粉们发掘中,细心的网友发现了一个非常人性化的功能,在iPhone的设置–通用–iPhone存储空间中,新增了一个“卸载未使用的应用”,点击启用后,当你的iPhone存储空间不足时会自动卸载手机里未使用的应用,但该应用的文稿与数据将会存储(该功能可在AppStore与itunesstore中关闭)。 当然,我们也可以自己手动选择要卸载的应用。相对于IOS1…

    2022年7月17日
    760
  • win7分区工具教程(装系统分区工具使用方法)

    由于硬盘分区是GPT格式,所以使用激活工具激活Win7系统的时候,可能会提示“不支持的启动引导分区”或者“不支持gpt引导分区表激活”等提示,是因为我们传统的Win7激活工具采用的是MBR激活方式,GPT磁盘比较特殊,不支持gpt引导分区表激活,所以需要gptwin7激活工具才可以解决。那么GPT分区无法激活Win7怎么办?下面装机之家分享一下激活win7提示不支持的启动引导分区的解决方法。 GP…

    2022年5月11日
    920
  • 怎么做关键词优化排名,首页关键词排名优化技巧

    在网站建设的初期,我们不仅需要网站搭建环境、网站页面设计、网站布局完美,同时网站的内容、以及SEO优化都是必不可少的。网站seo怎么做?做seo,很大程度上就是做关键词排名,这个点显得尤为重要,将合适的关键词做到合适的位置,seo就成功了一大半。那么怎么做好关键词排名呢? SEO关键词优化提升网站搜索排名的秘籍 第一点,关键词的选择。由于关键词的类型越来越多,其中主关键词、副关键词、核心关键词、目…

    2022年7月20日
    600
  • xls文件打不开怎么办,教你四个方法简单恢复

    经常使用Excel编制表格,处理数据的朋友应该都遇到过"文件已损坏,无法打开",这种情况吧,昨天上午,小石想打开前天没有编制完的报表继续工作的时候,遇到了这种情况 当然,我已经修复了,于是,我就想着经常用电脑做表格数据的肯定会有很多人遇到这种情况,所以,我就决定写一篇关于Excel文件受损,无法打开的解决办法。 我下面写四种方法,前三种是由于Excel非正常退出,造成的文件无法打开用的方法,第四种…

    2022年9月4日
    890
  • 创业时代什么时候播出,其播出时间及平台介绍

    由安建执导,黄轩、Angelababy领衔主演的都市情感创业剧《创业时代》即将登陆荧屏。该剧改编自付遥的同名小说,讲述了软件工程师郭鑫年研发手机软件魔盒走上创业之路,在这个过程中与同行竞争,邂逅投资分析师那蓝收获爱情的故事。 《创业时代》开播时间在哪儿能看哪个电视台播出 中文名:创业时代 外文名:EntrepreneurialAge 出品公司:浙江华策影视股份有限公司 制片地区:中国大陆 拍摄地点…

    2022年7月10日
    1110
  • 历史记录怎么恢复,找回浏览器历史记录方法

    在大多数时候我们也许无意中清除了所有历史记录和网络数据或删除了特定的Safari历史记录,我们是否想要撤销这些决定并获取浏览历史记录? 今天我们就来展示一种在Mac上恢复已删除Safari历史记录的方法。 我们采用的办法需要依赖于Mac上的备份服务TimeMachine,它恰好提供了在Mac上恢复已删除的Safari历史记录的最简单方法,或者用它恢复任何已删除的文件,虽然本次我们的重点是Safar…

    2022年5月26日
    3560
  • itunes怎么导出照片,新版itunes导出照片教程

    iTunes备份中保存了手机中的所有数据,当然也包括手机中拍的照片及视频,那么我们该如何才可以将iTunes备份中的相片导出来呢?其实方法很简单,下面就跟着我来一步步地操作吧。 1,首先我们将iPhone手机(或iPad)连接到电脑上,再使用iTunes软件对其数据进行备份。如果已经进行过了备份的话,则可以略过此步骤。 2,接着在电脑上下载并安装“楼月免费iTunes备份管理器”,在窗口上就可以看…

    2022年7月20日
    1470
  • 五笔打字软件电脑版(五笔打字法自学的软件)

    搜狗五笔输入法是搜狗公司推出的一款功能非常全面实用的五笔输入法软件,且与当前互联网新一代的五笔输入法、传统输入法不同的是,搜狗五笔输入法不仅支持随身词库,即超前的网络同步功能,还兼容目前强大的搜狗拼音输入法的所有皮肤,而最大的亮点就是,如果不会使用或不太熟练运用五笔输入法的用户也可以下载使用,因为该软件支持五笔+拼音、纯五笔、纯拼音多种模式的选择,从而使得该软件可以适合更多人群。同时正是因为搜狗五…

    2022年5月5日
    860
  • 微信公众号推广价格是多少,月涨1万粉的公众号推广方法分享

    影响微信公众号广告收费标准的因素有哪些?这些都是微信公众号运营者在运营公众号时说要考虑的因素和问题。下面小编就来为大家简单讲解一下。 影响公众号广告收费标准的因素有很多的,当然最主要的是粉丝数,其次粉丝的活跃度、公众号针对的行业、地区等都是有关系的。 第一个:粉丝数1W左右 单图文硬广软广的价格都在700左右(当然文案是自己提供) 多图文第一条价格就200~700不等 第二个:粉丝数5W 单图文软…

    2022年8月22日
    550

发表回复

登录后才能评论

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信