Description of bfstree

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:

• add add --- add edge(s) to the graph
• copy_labels copy_labels(g,h) --- copy labels from h to g
• embed embed --- create an embedding for a graph
• getxy getxy(g) --- give g's embedding (or [] if g doesn't have one)
• hasxy hasxy(g) --- determine if an embedding has been created for g
• is_labeled is_labeled(g) --- determine if there are labels on vertices.
• issparse issparse(g) --- check if g's adjacency matrix is sparse
• neighbors neighbors(g,v) --- neighbors of v as a list.
• nv nv(g) --- number of vertices in g
• resize resize(g,n) --- change the number of vertices in g to n
• sparse sparse(g) --- convert internal storage for g to sparse

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