def MinimumSpanningTree(G):
 if (not isUndirected(G)):
  raise ValueError('MinimumSpanningTree: input is not undirected')
 for u in G:
  for v in G[u]:
   if (G[u][v] != G[v][u]):
    raise ValueError('MinimumSpanningTree: asymmetric weights')
 subtrees = UnionFind()
 tree = []
 for (W, u, v) in sorted(((G[u][v], u, v) for u in G for v in G[u])):
  if (subtrees[u] != subtrees[v]):
   tree.append((u, v))
   subtrees.union(u, v)
 return tree

def MinimumSpanningTree ( G ) : if ( not isUndirected ( G ) ) : raise ValueError ( 'MinimumSpanningTree: input is not undirected' ) for u in G : for v in G [ u ] : if ( G [ u ] [ v ] != G [ v ] [ u ] ) : raise ValueError ( 'MinimumSpanningTree: asymmetric weights' ) subtrees = UnionFind ( ) tree = [ ] for ( W , u , v ) in sorted ( ( ( G [ u ] [ v ] , u , v ) for u in G for v in G [ u ] ) ) : if ( subtrees [ u ] != subtrees [ v ] ) : tree . append ( ( u , v ) ) subtrees . union ( u , v ) return tree
return the minimum spanning tree of an undirected graph g .