问题

最小生成树的Kruskal算法 描述：有A、B、C、D四个点，每两个点之间的距离（无方向）是(第一个数字是两点之间距离，后面两个字母代表两个点）：(1,’A’,’B’),(5,’A’,’C’),(3,’A’,’D’),(4,’B’,’C’),(2,’B’,’D’),(1,’C’,’D’)
生成边长和最小的树，也就是找出一种连接方法，将各点连接起来，并且各点之间的距离和最小。

思路说明：

Kruskal算法是经典的无向图最小生成树解决方法。此处列举两种python的实现方法。这两种方法均参考网上，并根据所学感受进行了适当改动。

解决1（Python）

  1.   1. #! /usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4. #以全局变量X定义节点集合，即类似{'A':'A','B':'B','C':'C','D':'D'},如果A、B两点联通，则会更改为{'A':'B','B':'B",...},即任何两点联通之后，两点的值value将相同。
  4.     5.   6. X = dict()      
  5.     7.   8. #各点的初始等级均为0,如果被做为连接的的末端，则增加1
  6.     9.   10. R = dict()
  7.     11.   12. #设置X R的初始值
  8.     13.   14. def make_set(point):
  9.     15.     X[point] = point
  10.     16.     R[point] = 0
  11.     17.   18. #节点的联通分量
  12.     19.   20. def find(point):
  13.     21.     if X[point] != point:
  14.     22.         X[point] = find(X[point])
  15.     23.     return X[point]
  16.     24.   25. #连接两个分量（节点）
  17.     26.   27. def merge(point1,point2):
  18.     28.     r1 = find(point1)
  19.     29.     r2 = find(point2)
  20.     30.     if r1 != r2:
  21.     31.         if R[r1] > R[r2]:
  22.     32.             X[r2] = r1
  23.     33.         else:
  24.     34.             X[r1] = r2
  25.     35.             if R[r1] == R[r2]: R[r2] += 1
  26.     36.   37. #KRUSKAL算法实现
  27.     38.   39. def kruskal(graph):
  28.     40.     for vertice in graph['vertices']:
  29.     41.         make_set(vertice)
  30.     42.   43.     minu_tree = set()
  31.     44.   45.     edges = list(graph['edges'])
  32.     46.     edges.sort()                    #按照边长从小到达排序
  33.     47.     for edge in edges:
  34.     48.         weight, vertice1, vertice2 = edge
  35.     49.         if find(vertice1) != find(vertice2):
  36.     50.             merge(vertice1, vertice2)
  37.     51.             minu_tree.add(edge)
  38.     52.     return minu_tree
  39.     53.   54.   55. if __name__=="__main__":
  40.     56.   57.     graph = {
  41.     58.         'vertices': ['A', 'B', 'C', 'D', 'E', 'F'],
  42.     59.         'edges': set([
  43.     60.             (1, 'A', 'B'),
  44.     61.             (5, 'A', 'C'),
  45.     62.             (3, 'A', 'D'),
  46.     63.             (4, 'B', 'C'),
  47.     64.             (2, 'B', 'D'),
  48.     65.             (1, 'C', 'D'),
  49.     66.             ])
  50.     67.         }
  51.     68.   69.     result = kruskal(graph)
  52.     70.     print result
  53.     71.   72. """
  54.     73. 参考:
  55.     74. 1.https://github.com/qiwsir/Algorithms-Book--Python/blob/master/5-Greedy-algorithms/kruskal.py
  56.     75. 2.《算法基础》(GILLES Brassard,Paul Bratley)
  57.     76. """

解决2（Python）

以下代码参考http://www.ics.uci.edu/~eppstein/PADS/的源码

  1.   1. #! /usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4. import unittest
  4.     5.   6. class UnionFind:
  5.     7.     """
  6.     8.     UnionFind的实例：
  7.     9.     Each unionFind instance X maintains a family of disjoint sets of
  8.     10.     hashable objects, supporting the following two methods:
  9.     11.   12.     - X[item] returns a name for the set containing the given item.
  10.     13.       Each set is named by an arbitrarily-chosen one of its members; as
  11.     14.       long as the set remains unchanged it will keep the same name. If
  12.     15.       the item is not yet part of a set in X, a new singleton set is
  13.     16.       created for it.
  14.     17.   18.     - X.union(item1, item2, ...) merges the sets containing each item
  15.     19.       into a single larger set.  If any item is not yet part of a set
  16.     20.       in X, it is added to X as one of the members of the merged set.
  17.     21.     """
  18.     22.   23.     def __init__(self):
  19.     24.         """Create a new empty union-find structure."""
  20.     25.         self.weights = {}
  21.     26.         self.parents = {}
  22.     27.   28.     def __getitem__(self, object):
  23.     29.         """Find and return the name of the set containing the object."""
  24.     30.   31.         # check for previously unknown object
  25.     32.         if object not in self.parents:
  26.     33.             self.parents[object] = object
  27.     34.             self.weights[object] = 1
  28.     35.             return object
  29.     36.   37.         # find path of objects leading to the root
  30.     38.         path = [object]
  31.     39.         root = self.parents[object]
  32.     40.         while root != path[-1]:
  33.     41.             path.append(root)
  34.     42.             root = self.parents[root]
  35.     43.   44.         # compress the path and return
  36.     45.         for ancestor in path:
  37.     46.             self.parents[ancestor] = root
  38.     47.         return root
  39.     48.   49.     def __iter__(self):
  40.     50.         """Iterate through all items ever found or unioned by this structure."""
  41.     51.         return iter(self.parents)
  42.     52.   53.     def union(self, *objects):
  43.     54.         """Find the sets containing the objects and merge them all."""
  44.     55.         roots = [self[x] for x in objects]
  45.     56.         heaviest = max([(self.weights[r],r) for r in roots])[1]
  46.     57.         for r in roots:
  47.     58.             if r != heaviest:
  48.     59.                 self.weights[heaviest] += self.weights[r]
  49.     60.                 self.parents[r] = heaviest
  50.     61.   62.   63. """
  51.     64. Various simple functions for graph input.
  52.     65.   66. Each function's input graph G should be represented in such a way that "for v in G" loops through the vertices, and "G[v]" produces a list of the neighbors of v; for instance, G may be a dictionary mapping each vertex to its neighbor set.
  53.     67.   68. D. Eppstein, April 2004.
  54.     69. """
  55.     70.   71. def isUndirected(G):
  56.     72.     """Check that G represents a simple undirected graph."""
  57.     73.     for v in G:
  58.     74.         if v in G[v]:
  59.     75.             return False
  60.     76.         for w in G[v]:
  61.     77.             if v not in G[w]:
  62.     78.                 return False
  63.     79.     return True
  64.     80.   81.   82. def union(*graphs):
  65.     83.     """Return a graph having all edges from the argument graphs."""
  66.     84.     out = {}
  67.     85.     for G in graphs:
  68.     86.         for v in G:
  69.     87.             out.setdefault(v,set()).update(list(G[v]))
  70.     88.     return out
  71.     89.   90.   91. """
  72.     92. Kruskal's algorithm for minimum spanning trees. D. Eppstein, April 2006.
  73.     93. """
  74.     94.   95. def MinimumSpanningTree(G):
  75.     96.     """
  76.     97.     Return the minimum spanning tree of an undirected graph G.
  77.     98.     G should be represented in such a way that iter(G) lists its
  78.     99.     vertices, iter(G[u]) lists the neighbors of u, G[u][v] gives the
  79.     100.     length of edge u,v, and G[u][v] should always equal G[v][u].
  80.     101.     The tree is returned as a list of edges.
  81.     102.     """
  82.     103.     if not isUndirected(G):
  83.     104.         raise ValueError("MinimumSpanningTree: input is not undirected")
  84.     105.     for u in G:
  85.     106.         for v in G[u]:
  86.     107.             if G[u][v] != G[v][u]:
  87.     108.                 raise ValueError("MinimumSpanningTree: asymmetric weights")
  88.     109.   110.     # Kruskal's algorithm: sort edges by weight, and add them one at a time.
  89.     111.     # We use Kruskal's algorithm, first because it is very simple to
  90.     112.     # implement once UnionFind exists, and second, because the only slow
  91.     113.     # part (the sort) is sped up by being built in to Python.
  92.     114.     subtrees = UnionFind()
  93.     115.     tree = []
  94.     116.     for W,u,v in sorted((G[u][v],u,v) for u in G for v in G[u]):
  95.     117.         if subtrees[u] != subtrees[v]:
  96.     118.             tree.append((u,v))
  97.     119.             subtrees.union(u,v)
  98.     120.     return tree        
  99.     121.   122.   123. # If run standalone, perform unit tests
  100.     124.   125. class MSTTest(unittest.TestCase):
  101.     126.     def testMST(self):
  102.     127.         """Check that MinimumSpanningTree returns the correct answer."""
  103.     128.         G = {0:{1:11,2:13,3:12},1:{0:11,3:14},2:{0:13,3:10},3:{0:12,1:14,2:10}}
  104.     129.         T = [(2,3),(0,1),(0,3)]
  105.     130.         for e,f in zip(MinimumSpanningTree(G),T):
  106.     131.             self.assertEqual(min(e),min(f))
  107.     132.             self.assertEqual(max(e),max(f))
  108.     133.   134. if __name__ == "__main__":
  109.     135.     unittest.main()

整理人：豆包AI助手