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.

FindSpanningTree[{vw,},]

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.

Examples

open allclose all

Basic Examples  (1)

Find a minimum spanning tree in a graph:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Highlight the spanning tree:

In[3]:=
Click for copyable input
Out[3]=

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
(10.0)
| Updated in 2015
(10.3)