龙空技术网

从《文明》游戏如何修路到数学中的最小生成树算法

宇宙文明领路人 208

前言:

此时兄弟们对“最小生成树的克鲁斯卡尔算法数据结构c语言”大致比较讲究,各位老铁们都想要学习一些“最小生成树的克鲁斯卡尔算法数据结构c语言”的相关内容。那么小编也在网摘上搜集了一些有关“最小生成树的克鲁斯卡尔算法数据结构c语言””的相关知识,希望咱们能喜欢,同学们一起来学习一下吧!

女士们,先生们,老少爷们儿们!在下张大少。

《文明》游戏想来诸位并不陌生,筑成后需要在城市之间修路。在下这种懒癌晚期的玩家,显然会把这种无聊的工作委任给电脑。但说出来你可能不信,高手认为这其中蕴含着数学算法。

如图:把6座城市连起来,且道路的总长度越小越好。可有方法?

闲言少叙,且看在下操作!

首先简化游戏画面,6座城市分别为A、B、C、D、E、F,两两之间标上距离。

由此可见,我们要求解的是上图的一个子图。此图要求6座城市相互连接,同时路的总长度最短。这便是数学中的最小生成树问题。

求解最小生成树有两种经典算法。一是普利姆(Prim)算法;二是克鲁斯卡尔(Kruskal)算法。

我们先看普利姆算法:

Step1,任取一顶点,我们取顶点A。

Step2,与A相连的边有3条,AB、AC、AD,取最短的边AB。

Step3,与A、B相连的边有4条,AC、AD、BE、BF,取最短的边AD。

Step4,与A、B、D相连的边有5条,AC、CD、BE、BF、DE,取最短的边CD。

Step5,与A、B、C、D相连的边有4条,AC、BE、BF、DE,取最短的边BE。

Step6,与A、B、C、D、E相连的边有4条,AC、BF、DE、EF,取最短的边EF。

搞定!6座城市皆已连通,可知道路的总长度为20。

接下来看看克鲁斯卡尔算法:

Step1,先把原图中的边删掉,只保留6座城市。

Step2,在所有边中找出长度最短的一条,即AB=3。

Step3,在剩余的边中继续找长度最短的边,此时AD、CD、EF都是4,观察可知A、C、D、E、F都在不同的连同分量上,所以把这三条边加入进来。

Step4,在剩余的边中继续找长度最短的边,即BE=5,观察可知B、E分属两个不同的连同分量,所以把BE加进来。

搞定!结果跟普利姆算法一模一样!不用说也知道,这便是最优解。

游戏中修路如此,实际生活中的很多问题也如出一辙,例如城市之间铺设光缆,轨道建设,工程布网等,实际上都可以抽象成最小生成树问题。掌握以上两种算法,此类问题便迎刃立解。

张大少友情提醒:两种算法功能等效,但适用条件有所不同。因为二者的时间复杂度不同。普利姆算法适用于求解边稠密而顶点不多的场合;而克鲁斯卡尔算法适用于求解边稀疏的场合。若要深入了解,请老少爷们参考相关的算法教程,在下不再赘述。

青山不改,绿水长流,在下告退。

转发随意,转载请联系张大少本尊。

标签: #最小生成树的克鲁斯卡尔算法数据结构c语言 #克鲁斯卡尔算法求最小生成树c语言 #普利姆算法与克鲁斯卡尔 #普利姆算法与克鲁斯卡尔算法区别 #普利姆算法与克鲁斯卡尔算法区别是什么