问题：

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

解决：

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

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

ruby实现：

我准备了三个文件：

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

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

quick_sort文件是快速排序算法

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

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

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

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

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

python实现

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

共三个文件

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

union.py

然后是make_tree.py文件。

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