Important: The networks package has been deprecated.Use the superseding command GraphTheory[MinimalSpanningTree] instead.

This routine constructs a spanning tree for the graph G.  The result is returned as a new graph derived from G and consisting of that spanning tree.

The chosen tree has edges which minimize the total edge weight of the tree.

The routine uses Prim's algorithm, which fails if G is not strongly connected.

The routine is normally loaded via the command with(networks) but may also be referenced using the full name networks[spantree](...).

$\mathrm{with}\left(\mathrm{networks}\right)\:$

$G≔\mathrm{petersen}\left(\right)\:$

$\mathrm{ends}\left(G\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,5\right\}\,\left\{1\,6\right\}\,\left\{2\,3\right\}\,\left\{2\,8\right\}\,\left\{3\,4\right\}\,\left\{3\,10\right\}\,\left\{4\,5\right\}\,\left\{4\,7\right\}\,\left\{5\,9\right\}\,\left\{6\,7\right\}\,\left\{6\,10\right\}\,\left\{7\,8\right\}\,\left\{8\,9\right\}\,\left\{9\,10\right\}\right\}$

$\mathrm{spantree}\left(G\,1\,w\right)$

$\mathbf{proc}\left(x\right)\mathbf{option}\mathrm{GRAPH}\,2\;\mathbf{if}x\=\mathrm{\_Edges}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Edges}\right)≔\left\{\right\}\mathbf{elif}x\=\mathrm{\_EdgeIndex}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_EdgeIndex}\right)≔\mathrm{table}\left(\mathrm{symmetric}\right)\mathbf{elif}x\=\mathrm{\_Head}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Head}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Tail}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Tail}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Eweight}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Eweight}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Ends}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Ends}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Vertices}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Vertices}\right)≔\left\{\right\}\mathbf{elif}x\=\mathrm{\_Vweight}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Vweight}\right)≔\mathrm{table}\left(\mathrm{sparse}\right)\mathbf{elif}x\=\mathrm{\_Ancestor}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Ancestor}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Daughter}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Daughter}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Neighbors}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Neighbors}\right)≔\mathrm{table}\left(\right)\mathbf{elif}x\=\mathrm{\_Status}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Status}\right)≔\left\{\'\mathrm{SIMPLE}\'\right\}\mathbf{elif}x\=\mathrm{\_Emaxname}\mathbf{then}\mathrm{thisproc}\left(\mathrm{\_Emaxname}\right)≔0\mathbf{else}\mathbf{return}\'\mathrm{procname}\left(\mathrm{args}\right)\'\mathbf{end\; if}\mathbf{end\; proc}$

$\mathrm{ends}\left(\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,6\right\}\,\left\{2\,8\right\}\,\left\{3\,10\right\}\,\left\{4\,5\right\}\,\left\{4\,7\right\}\,\left\{5\,9\right\}\,\left\{6\,10\right\}\,\left\{8\,9\right\}\right\}$

$w$

$9$