Home > matgraph > @graph > bfstree.m

bfstree

PURPOSE ^

bfstree(t,g,v) --- create a breadth-first spanning tree of g

SYNOPSIS ^

function bfstree(t,g,v)

DESCRIPTION ^

 bfstree(t,g,v) --- create a breadth-first spanning tree of g
 The tree is rooted a the vertex v (or vertex 1 if missing). If g is not
 connected, we generate a tree only for the component containing v;
 vertices in the other components are isolated vertices in t.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function bfstree(t,g,v)
0002 % bfstree(t,g,v) --- create a breadth-first spanning tree of g
0003 % The tree is rooted a the vertex v (or vertex 1 if missing). If g is not
0004 % connected, we generate a tree only for the component containing v;
0005 % vertices in the other components are isolated vertices in t.
0006 
0007 
0008 
0009 if nargin==2
0010     v = 1;
0011 end
0012 
0013 n = nv(g);
0014 if (v<0) | (v>n)
0015     error('Seed vertex out of range')
0016 end
0017 
0018 if (issparse(g))
0019     sparse(t)
0020 end
0021 resize(t,0);
0022 resize(t,n);
0023 
0024 
0025 q_init(n+1);
0026 
0027 visited = zeros(n,1);
0028 visited(v) == 1;
0029 q_push(v);
0030 
0031 while(q_size > 0)
0032     x = q_pop_front;
0033     nlist = neighbors(g,x);
0034     for w = nlist
0035         if (visited(w)==0)
0036             visited(w) = 1;
0037             add(t,x,w);
0038             q_push(w);
0039         end
0040     end
0041 end
0042 
0043 
0044 if hasxy(g)
0045     embed(t,getxy(g))
0046 end
0047 
0048 if is_labeled(g)
0049     copy_labels(t,g);
0050 end
0051

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003