Finding spanning trees
Matgraph provides two functions for finding spanning trees:
- bfsptree --- breadth first spanning tree
- dfsptree --- depth first spanning tree
Contents
Set up the graph
We illustrate finding spanning trees in the icosahedron graph.
g = graph; icosahedron(g);
Depth first spanning tree
t = graph;
dfstree(t,g);
clf; draw(g,':');
draw(t)

Breadth first spanning tree
bfstree(t,g);
clf; draw(g,':');
draw(t)

Counting spanning trees
The matrix-tree theorem makes enumerating spanning trees in Matlab especially easy.
nt = nsptrees(g); disp(['The icosahedron graph has ', int2str(nt),' spanning trees']);
The icosahedron graph has 5184000 spanning trees
Release the graphs
free(t) free(g)