FindSpanningTree

FindSpanningTree[g]
finds a spanning tree of the graph g.

FindSpanningTree[{g,v},]
finds a spanning tree of the connected component of g that includes the vertex v.

Details and OptionsDetails and Options

  • FindSpanningTree is also known as minimum spanning tree and spanning forest.
  • A spanning tree of a connected graph g is a subgraph of g that is a tree and connects all vertices of g.
  • For weighted graphs, FindSpanningTree gives a spanning tree with minimum sum of edge weights.
  • For disconnected graphs, FindSpanningTree gives a subgraph that consists of a spanning tree for each of its connected components.
  • FindSpanningTree takes the same options as Graph.
  • Possible settings for Method include , , and . The default setting of Automatic switches among these methods depending on the graph given.
  • FindSpanningTree works with undirected graphs, directed graphs, weighted graphs, and multigraphs.
Introduced in 2014
(10.0)