python和ruby实现最小生成树算法

问题:

python和ruby实现最小生成树算法

有六个城市,之间的道路如上图所示。中间的数字表示,连接两个城市的建立道路所花费的金钱数。那么如何建立道路,才能在使用最小金钱的情况下,把各个城市都连接起来呢。

解决:

这是一个最小生成树问题。连接n个城市,最少需要n-1条道路。我们先把金钱数按从小到达排序,然后按金钱数从小到大选择对应的道路。这时我们会用到查并集的算法来判断两个城市是否已经联通,如果联通就查看下一条道路,否则将这条道路选择,并对这两个城市进行并集操作,直到我们得到n-1条道路。(大家可以去查看我之前关于查并集算法的文章。)

下面我们来看ruby和python的代码实现:

ruby实现:

我准备了三个文件:

python和ruby实现最小生成树算法

其中data是用来记录数据的:

python和ruby实现最小生成树算法

前两个数表示城市,第三个数代表金钱数。

quick_sort文件是快速排序算法

python和ruby实现最小生成树算法

大家可以看前面的文章。用ruby实现算法3 快速排序

然后是我们的主程序了,首先是初始化部分:

python和ruby实现最小生成树算法

接着是两个查并集的函数,大家可以看前面的文章:

python和ruby实现最小生成树算法

然后是从data中读取数据,加入字典,将金钱数设为key值,将城市设为value。然后对key进行升序排序,根据这个顺序,计算查并集,选择路径。

python和ruby实现最小生成树算法

但其实这个算法有个特别大的问题,就是把金钱设为key了,因为key值是不能重复的。应该把城市数组设为key值。但我懒得改了,留个大家尝试。

python实现

python实现和上面的思路一样,我们直接上代码

python和ruby实现最小生成树算法

共三个文件

data与上面的一样。union.py我在前一个文章中讲过。

python和ruby实现最小生成树算法

union.py

然后是make_tree.py文件。

python和ruby实现最小生成树算法

python和ruby实现最小生成树算法

这里使用了二维数组来处理数据。


鲜花

握手

雷人

路过

鸡蛋
用心服务创业者
0851-88611148
周一至周五 9:00-18:00
意见反馈:admin@0851life.com

扫一扫关注我们

Powered by 童码少儿编程 X3.4© 2001-2013 0851life Inc.|网站地图