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.
D. Eppstein, April 2004.
"""
defisUndirected(G):
"""Check that G represents a simple undirected graph."""
forvinG:
ifvinG[v]:
returnFalse
forwinG[v]:
ifvnotinG[w]:
returnFalse
returnTrue
defunion(*graphs):
"""Return a graph having all edges from the argument graphs."""
out= {}
forGingraphs:
forvinG:
out.setdefault(v,set()).update(list(G[v]))
returnout
"""
Kruskal's algorithm for minimum spanning trees. D. Eppstein, April 2006.
"""
importunittest
defMinimumSpanningTree(G):
"""
Return the minimum spanning tree of an undirected graph G.
G should be represented in such a way that iter(G) lists its
vertices, iter(G[u]) lists the neighbors of u, G[u][v] gives the
length of edge u,v, and G[u][v] should always equal G[v][u].
The tree is returned as a list of edges.
"""
ifnotisUndirected(G):
raiseValueError("MinimumSpanningTree: input is not undirected")