finds a spanning tree of the graph g.


finds a spanning tree of the connected component of g that includes the vertex v.


uses rules vw to specify the graph g.

Details 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 "Prim", "Kruskal", and "MinimumCostArborescence". 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.


open allclose all

Basic Examples  (1)

Find a minimum spanning tree in a graph:

Click for copyable input
Click for copyable input

Highlight the spanning tree:

Click for copyable input

Scope  (7)

Generalizations & Extensions  (1)

Options  (5)

Applications  (5)

Properties & Relations  (3)

Possible Issues  (1)

Neat Examples  (1)

See Also

TreeGraph  DepthFirstScan  BreadthFirstScan

Introduced in 2014
| Updated in 2015