Description of dfstree

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:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• copy copy(g,h) --- overwrite g with a copy of h
• 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.
• neighbors neighbors(g,v) --- neighbors of v as a list.
• nv nv(g) --- number of vertices in g

This function is called by:

SUBFUNCTIONS

• function visited = tree_build(t,g,v,visited)

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