Home > matgraph > @graph > dfstree.m

dfstree

PURPOSE ^

dfstree(t,g,v) --- create a depth-first spanning tree of g

SYNOPSIS ^

function dfstree(t,g,v)

DESCRIPTION ^

 dfstree(t,g,v) --- create a depth-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:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function dfstree(t,g,v)
0002 % dfstree(t,g,v) --- create a depth-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 copy(t,g);
0019 clear_edges(t);
0020 
0021 q_init(2*n+1);
0022 
0023 visited = zeros(n,1);
0024 tree_build(t,g,v,visited);
0025     
0026    
0027 if is_labeled(g)
0028     copy_labels(t,g);
0029 end
0030 
0031 
0032 if hasxy(g)
0033     embed(t,getxy(g))
0034 end
0035 
0036 end
0037 
0038 
0039 function visited = tree_build(t,g,v,visited)
0040 % recursively build DFS tree
0041 
0042 visited(v) = 1;
0043 
0044 nlist = neighbors(g,v);
0045 
0046 for w = nlist
0047     if (~visited(w))
0048         add(t,v,w);
0049         visited = tree_build(t,g,w,visited);
0050     end
0051 end
0052         
0053 
0054 
0055 
0056 
0057 end

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