女士们，先生们，老少爷们儿们！在下张大少。
《文明》游戏想来诸位并不陌生，筑成后需要在城市之间修路。在下这种懒癌晚期的玩家，显然会把这种无聊的工作委任给电脑。但说出来你可能不信，高手认为这其中蕴含着数学算法。
如图：把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加进来。
搞定！结果跟普利姆算法一模一样！不用说也知道，这便是最优解。
游戏中修路如此，实际生活中的很多问题也如出一辙，例如城市之间铺设光缆，轨道建设，工程布网等，实际上都可以抽象成最小生成树问题。掌握以上两种算法，此类问题便迎刃立解。
张大少友情提醒：两种算法功能等效，但适用条件有所不同。因为二者的时间复杂度不同。普利姆算法适用于求解边稠密而顶点不多的场合；而克鲁斯卡尔算法适用于求解边稀疏的场合。若要深入了解，请老少爷们参考相关的算法教程，在下不再赘述。
青山不改，绿水长流，在下告退。
转发随意，转载请联系张大少本尊。
