问题

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

解决2(Python)

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

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