登陆注册
37240300000155

第155章 最小生成树(下)

那么,就开始编写Prim算法吧!

首先,做异常情况判断。

两种情况视为异常:

1.地图为空(没有意义嘛)

2.地图连通性无法保证

这些情况,通通返回空地图。

然后,从地图中选取一个点,作为起始顶点。

随便哪个点都可以的!

将该点标识为已访问,并将含有起始顶点的边添加到优先级队列。

接下来,是算法的关键性部分。

1.从优先级队列中取出权重最小的边。

2.如果这条边,两端的点都被访问过,说明是失效的边,将其舍弃。

3.这条边没有被舍弃,那就是有效的,加入最小生成树。

4.以这条边,没有被访问过的端点,继续标识为已访问,并将含有该端点的边添加到优先级队列。

5.又从1.开始,反复循环。

这似乎是个从1到4阶段永不停歇的贪心计算过程。

然而,万物有始必有终结。

当图中所有的顶点,都被最小生成树得到(顶点数量相同)。

或者,当优先级队列为空。

这个算法就结束了它的使命。

此时得到的,就是原来地图的最小生成树。

同类推荐
  • 快穿之原来我是NPC

    快穿之原来我是NPC

    失忆的智障女主的装逼之路,女主不是人蠢作者是简介废,第一次写文,请多包涵。(PS:蠢猫不喜欢攻略来攻略去的,想看攻略的小天使们慢走不送)我是谁?这是辛笙醒来的第一个念头。【叮,这里是时空之巅……】来自早已被入侵仍不自知的蠢系统。愚蠢的人们,你以为这里是一篇正经的快穿文吗?哈哈,没错,你猜对了ヾ(????)?~一般的快穿开头都是女主死了然后怎样的,但这个是一篇探寻身份的倒叙文,女主很流弊,所以不要问女主为啥知道辣么多类似于bug的。。。这好像是个不正经的简介(?▽`)
  • 科技,毁灭还是创造

    科技,毁灭还是创造

    科技,毁灭还是创造?本小说将带领您走向科幻的道路
  • 老子是神话

    老子是神话

    生、死之间不仅仅是睁眼和闭眼的区别,因为我闭上眼,是一片血红,睁开眼,是血红一片。我没想过自己会成为救世主,我只是渴望自己能活下去。美女?皮囊罢了。成为我的女人,首先,你要有一个让我接受你的理由。
  • 星河战尊

    星河战尊

    这是一个波澜绚丽的星河时代!古武机甲与外星科技对抗,超术异能与异形种族争锋!机甲领域的王者,有着“战神”之称的林锋在一次古遗迹争夺中陨落,重生回到了十年前——在重生记忆的改变下,曾经的遗憾,都将补全,曾经的传奇,也将更辉煌的开始!
  • 穿越之平行境

    穿越之平行境

    一次意外的空难使得屌丝王大宝和空姐李英子落入神秘困境,在脱困之后发生一连串的奇遇。未来世界?未来战争?僵尸异形?到底是什么在前方?背后又有怎样的阴谋?
热门推荐
  • 特务九课

    特务九课

    这里是处于魔法科技时代的世界,管理着各个平行世界的次元管理局突然成立了一个名叫特务九课独立部队的部队,而我们人畜无害的女主角史黛拉竟被选为了其先锋队的一员。极端组织〈暮瞳〉的黑手正蠢蠢欲动。史黛拉即将迎来的究竟是什么?
  • 残佞总裁的天真妻

    残佞总裁的天真妻

    林辰翼,认为世界上所有的女人都是一样的,都会对他着迷。只有尹夏,仿佛把他的吸引力当成了祸害。尹夏,本就被一团事情弄得炸毛,还被男友抛弃,哪有时间理他。林辰翼无奈,男人中也有好东西,至少他是!
  • 无限之神迹

    无限之神迹

    主角通过无限世界一步步进化最终找回自我。早先安排好的后手,神秘的身份。这恐怖的空间到底由谁所造?所有的秘密一一揭开。
  • 这根本不是我想要的日常

    这根本不是我想要的日常

    乾宇:“姐姐大人们,你们不要这样好嘛?我好害怕。”蓉姐:“嘿嘿,宝贝小宇,你就乖乖从了姐姐们吧!”倩姐:“呜…蓉儿,我们这样做是不是不太好呀?……”
  • 假面骑士和奥特曼的乱斗系统

    假面骑士和奥特曼的乱斗系统

    他,能穿越任意一个世界,能变成任意一个奥特曼和假面骑士。最终将成为这片天地的主宰。
  • 称霸异界之英雄崛起

    称霸异界之英雄崛起

    一名平凡的地球人在异界大陆成为一代天骄的传说!
  • 镜面人之暮夜

    镜面人之暮夜

    当时,林秋寒不喜不悲的表情,和那双鲜少露出孤单情绪的眼睛,看起来格外的凄凉,他说:“我只希望自己能够在旋涡中,一直保有一丝理念。”这个世界充满了黑暗,如果你喜欢在光明里生长,那么就由我来为你承担那些黑暗里的血雨风雨。
  • 蔷薇花语的美好心情

    蔷薇花语的美好心情

    蔷薇的心境。如同美好的时光。总是那么短暂。人生又的确不是这样呢
  • 凤华绝黛:摄政王妃不下朝

    凤华绝黛:摄政王妃不下朝

    青天之上,白砾天宫,一朝凤族圣女,透过泉鸾镜看了人间十几世纪,勾起嫣红的唇,满脸向往。“真想去凡人的世界转转啊。”当要继承凤族族长之时,却天皇无情拿下。“冒充圣女之人,当立即除去仙骨,永世不得超生。”天皇无情的下了命令,她被推下诛仙台之时,蓦然回首,只见当时自己救下的那只小青鸟嘴角挂着嘲讽的笑,高坐在族长之位,轻蔑的居高临下看着她。“姐姐,真没想到,你会如此狼狈。”她的泪,随着风飞向诛仙台,绝情又狠心的,泯灭了所有的期翼,承受着剔除仙骨带来的疼痛,凭借着强大的执念,活了下来。当她看着缩小版的小嫩手,和眼前笑意下暗潮汹涌的他,耳内接受了他柔情的话语——“小汐儿,你终于肯醒来了。”
  • 女配想静静

    女配想静静

    车祸穿越,既来之则安之,但尼玛竟然穿到书里,还是个连女二女三都算不上的小配角。她自认为没有通天本领在古代活得多姿多彩,欲仙欲死。所以咱远离男主女主,安安稳稳过咱小日子行不。不过boss,咱俩不合适呀,我有喜欢的人了!哦,原来那人是你呀,这可咋整?这是个从弱小小丫鬟逐渐成长,变得强大最终收获爱情!本文女主无金手指。开始弱小,没有远大志向,后期慢慢成长起来,1V1,HE。