问题

思路说明：

解决1（Python）

解决2（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]
  43.         # compress the path and return
  44.         for ancestor in path:
  46.         return root
  48.     def __iter__(self):
  49.         """Iterate through all items ever found or unioned by this structure."""
  50.         return iter(self.parents)
  52.     def union(self, *objects):
  53.         """Find the sets containing the objects and merge them all."""
  54.         roots = [self[x] for x in objects]
  55.         heaviest = max([(self.weights[r],r) for r in roots])[1]
  56.         for r in roots:
  57.             if r != heaviest:
  58.                 self.weights[heaviest] += self.weights[r]
  59.                 self.parents[r] = heaviest
  62. """
  63. Various simple functions for graph input.
  65. 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.
  67. D. Eppstein, April 2004.
  68. """
  70. def isUndirected(G):
  71.     """Check that G represents a simple undirected graph."""
  72.     for v in G:
  73.         if v in G[v]:
  74.             return False
  75.         for w in G[v]:
  76.             if v not in G[w]:
  77.                 return False
  78.     return True
  81. def union(*graphs):
  82.     """Return a graph having all edges from the argument graphs."""
  83.     out = {}
  84.     for G in graphs:
  85.         for v in G:
  86.             out.setdefault(v,set()).update(list(G[v]))
  87.     return out
  90. Kruskal's algorithm for minimum spanning trees. D. Eppstein, April 2006.
  91. """
  93. def MinimumSpanningTree(G):
  94.     """
  95.     Return the minimum spanning tree of an undirected graph G.
  96.     G should be represented in such a way that iter(G) lists its
  97.     vertices, iter(G[u]) lists the neighbors of u, G[u][v] gives the
  98.     length of edge u,v, and G[u][v] should always equal G[v][u].
  99.     The tree is returned as a list of edges.
  100.     """
  101.     if not isUndirected(G):
  102.         raise ValueError("MinimumSpanningTree: input is not undirected")
  103.     for u in G:
  104.         for v in G[u]:
  105.             if G[u][v] != G[v][u]:
  106.                 raise ValueError("MinimumSpanningTree: asymmetric weights")
  108.     # Kruskal's algorithm: sort edges by weight, and add them one at a time.
  109.     # We use Kruskal's algorithm, first because it is very simple to
  110.     # implement once UnionFind exists, and second, because the only slow
  111.     # part (the sort) is sped up by being built in to Python.
  112.     subtrees = UnionFind()
  113.     tree = []
  114.     for W,u,v in sorted((G[u][v],u,v) for u in G for v in G[u]):
  115.         if subtrees[u] != subtrees[v]:
  116.             tree.append((u,v))
  117.             subtrees.union(u,v)
  118.     return tree        
  121. # If run standalone, perform unit tests
  123. class MSTTest(unittest.TestCase):
  124.     def testMST(self):
  125.         """Check that MinimumSpanningTree returns the correct answer."""
  126.         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}}
  127.         T = [(2,3),(0,1),(0,3)]
  128.         for e,f in zip(MinimumSpanningTree(G),T):
  129.             self.assertEqual(min(e),min(f))
  130.             self.assertEqual(max(e),max(f))
  132. if __name__ == "__main__":