def minimal_spanning_tree(graph, root=None):
visited = []            <EOL>spanning_tree = {}        <EOL>if (root is not None):<EOL><INDENT>visited.append(root)<EOL>nroot = root<EOL>spanning_tree[root] = None<EOL><DEDENT>else:<EOL><INDENT>nroot = <NUM_LIT:1><EOL><DEDENT>while (nroot is not None):<EOL><INDENT>ledge = _lightest_edge(graph, visited)<EOL>if (ledge == None):<EOL><INDENT>if (root is not None):<EOL><INDENT>break<EOL><DEDENT>nroot = _first_unvisited(graph, visited)<EOL>if (nroot is not None):<EOL><INDENT>spanning_tree[nroot] = None<EOL><DEDENT>visited.append(nroot)<EOL><DEDENT>else:<EOL><INDENT>spanning_tree[ledge[<NUM_LIT:1>]] = ledge[<NUM_LIT:0>]<EOL>visited.append(ledge[<NUM_LIT:1>])<EOL><DEDENT><DEDENT>return spanning_tree<EOL>
Minimal spanning tree.

@attention: Minimal spanning tree is meaningful only for weighted graphs.

@type  graph: graph
@param graph: Graph.

@type  root: node
@param root: Optional root node (will explore only root's connected component)

@rtype:  dictionary
@return: Generated spanning tree.