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
• Depth first spanning tree
• Breadth first spanning tree
• Counting spanning trees
• Release the graphs

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)

Published with MATLAB® 7.2