Editorial/Data Protection
Spanning Trees

The functions to get minimum spanning trees make use of two algorithms:

Algorithm   Application
Prim for dense graphs with many edges
Kruskal   for sparse graphs with few edges

The following functions are implemented to get spanning trees:

Function   Short Description
MinimumSpanningTree spanning tree with minimum cost
AnySpanningTree spanning tree
AnyDirectedSpanningTree directed spanning tree

The facing column contains an example for MinimumSpanningTree.

graph in list form

{18., {{1, 6}, {6, 4}, {4, 3}, {3, 2}, {6, 5}}}

plot spanning tree

Editorial/Data Protection • page checked on Nov. 28th 2005