问题

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

解决2（Python）

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

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