最小生成树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

相关推荐

  • 什么录屏软件好用,简单专业的录屏软件推荐

    前言 录屏软件是一种你虽然不会时刻在用,但是需要到的时候却不知从何下手的工具。该选择哪款录屏工具?当我们从各种平台下载录屏软件尝试之后会发现有各种各样的问题, 录制时长限制广告令人发指录制画质差劲 此前有位同学在我文章下留言“能推荐几款录屏软件吗?” 时间已经过去有段时间了,刚好近期我也需要录制一些简单的视频教程,所以在这几个月里我一直在留意、试用不同的录屏软件,今天就来介绍几款不错的录屏软件,各…

    2022年8月5日
    620
  • 网络公司推荐,国内最权威的六家互联网公司

    2018年7月28日,工业和信息化部信息中心官方网站发布了《2018年中国互联网企业100强榜单》。这个榜单显示了国内排名前100的互联网公司和各个公司的品牌、服务。 此次广东省内一共有14家互联网企业跻身百强榜单,分别来自深圳、广州和珠海三个城市,深圳的互联网百强企业数量最多达到8家,广州紧跟其后有5家互联网企业跻身上榜,最后一家企业是来自珠海的金山软件。 腾讯大厦 令人感到意外的是:广东互联网…

    2022年10月4日
    530
  • 网店转让平台哪个安全,最大最专业的网店转让平台推荐

    网店转让平台哪家好?哪个靠谱呢? 最近今年电商行业的发展越来越好,但竞争也是很大,尤其是天猫店铺,入驻都是很难很难,所以很多商家就通过网店转让平台购买一些老店来经营,不仅直接解决了入驻的问题,还大大增加了网店的开店成功几率。购买的老店都是一些有数据有流量的老店,很减少很多不必要的麻烦。 但是大家在购买选择的时候还是存在一些顾虑,为了能够更安全的完成交易,想选择一个靠谱的网店转让平台。那么哪家的网店…

    2022年7月12日
    570
  • 个人创业适合做什么项目,创业能力形成的途径有哪些

    随着创业找项目的人越来越多,赚钱的人越来越多,自然而然的就有人总结出来一些小技巧,这些小技巧虽然不能让创业者一定会赚很多钱,但是至少能够保证收益是持续增长的,那么来看看到底是什么小技巧。 一、合理利用人 创业资金是有限的,而且创业者要改变一个理念,创业不是人多就好的,创业要的是效率,没有效率,人再多也是没有用的,就好比创业者招5个人,一个岗位上就有两个人,他们会觉得自己不做的事情会有人去做,那么他…

    2022年5月18日
    680
  • qq邮件群发技巧,qq邮件群发软件哪个好

    关注搜索引擎尚未收录的网站内容 外贸内容优化,一直以来都在强调原创,问题在于,哪里来那么多的原创素材?专家有个好主意,那就是到还没有收录的网站中去,寻找素材。因为内容还没有被搜索引擎收录,所以,原创度上一定是够的。注意了,这里说的是参考,不是采集或者是复制粘贴,请尊重别人的劳动成果。 找同行网站未收录的文章 这种寻找外贸网站原创素材的方式其实和刚刚说的有些类似,重点在于寻找素材和创意。 到问答平台…

    2022年7月14日
    540
  • macbook换电池要多少钱(苹果笔记本a1502换电池教程)

    电量一直停留在1%、电脑连接电源后无法充电、更换新的电池后故障再次出现……一大批果粉最近因此焦头烂额。 近日,多位MacBook用户向《消费者报道》报料,称自己的MacBookPro近期突然出现无法充电的故障,问题主要集中在2017款MacBookPro上。由于不少消费者的电脑已经超过保修期,只能自费更换新的电池,不过更换电池后故障再次出现。 针对消费者反映的问题,苹果官方客服人员表示电脑无法充电…

    2022年8月22日
    1270
  • 丰巢后撤,便宜了菜鸟驿站、京东快递柜?

    在同行蚕食的压力下,提高优化自己的服务是必要的。能不能保住“智能快递柜一哥”的名号,还得看它的自身发展。

    2022年9月26日
    600
  • 单个关键词排名怎么做,2019十大热搜词汇

    想必应该是大部分企业个人工作室都已经在一年前意识到互联营销的重要性,都开始建设网站,然后进行网站推广以及营销工作,在进行SEO网站推广时,不管是个人还是企业更关心的是单个关键词在百度搜索引擎的排名,因此做为SEO的我们在做某个关键词的优化要区别对待整站优化,才能节省时间,要怎么做才能将单个关键词排名快速提升到百度首页?确定好核心关键词并做好网站关键词布局对于优化来说,网站的每一个细节都是至关重要。…

    2022年6月6日
    700
  • u盘上删除的文件怎么恢复,恢复u盘文件的软件推荐

    怎么恢复u盘删除的文件?本文教给大家u盘删除的文件恢复方法。U盘删除文件没有回收站可以一键恢复这一问题苦恼了一大波用户,今天小编就来告诉大家一个简单恢复U盘数据的办法。只要电脑上下载安装一个失易得数据恢复,当误删了U盘文件只要打开软件扫描预览,预览正常就可以直接一键恢复。   如果你有将重要文件保存拷贝到U盘的习惯,那么建议安装一个专业的数据恢复软件以防万一。失易得数据恢复软件的操作很简单,运行速…

    2022年6月27日
    1320
  • 莫斯奇诺香水专柜价格(关于莫斯奇诺的4款香水)

    香水可以说是提升两人甜蜜度的最佳礼物,让你爱的人拥有你爱的味道,无论你是初恋中的少男少女,还是结婚多年的老夫老妻,选择以下几款香水让你满分约会! 莫斯奇诺雾仙浓粉红甜心女士 这是一款明快浓烈且充满活力的香水,融合了闪亮与活力四射的感觉;佛手柑充满爆发性的清新感和菠萝冰糕那令人愉悦的感觉,牡丹与浪漫的粉色百合在神秘的茉莉花韵调的衬托下显得更加强烈;香水的花香主调饰以精致的姜饼,还有令人垂涎的桃子带来…

    2022年10月17日
    520

发表回复

登录后才能评论

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

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

关注微信