This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
RE: Breadth First Traversal
- To: xsl-list at lists dot mulberrytech dot com
- Subject: RE: [xsl] Breadth First Traversal
- From: Dan Diebolt <dandiebolt at yahoo dot com>
- Date: Wed, 2 May 2001 19:40:55 -0700 (PDT)
- Reply-To: xsl-list at lists dot mulberrytech dot com
Thanks. I need to study this a bit, but let me add two issues:
1) Can Breadth First Traversal be coded without <xsl:call-template>?
In other words, just use <xsl:apply-templates select="?">.
2) Is there a unified Breadth First and Depth First version as
outlined at the following URL:
http://www.ics.uci.edu/~eppstein/161/960215.html
In this case I would want a paramater for Breadth/Depth First
and expect to call the template.
Regards,
Dan
bfs(G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L nonempty)
remove edge (v,w) from start of L
if w not yet visited
{
add (v,w) to T
search(w)
}
}
dfs(G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L nonempty)
remove edge (v,w) from end of L
if w not yet visited
{
add (v,w) to T
search(w)
}
}
search(vertex v)
{
visit(v);
for each edge (v,w)
add edge (v,w) to end of L
}
__________________________________________________
Do You Yahoo!?
Yahoo! Auctions - buy the things you want at great prices
http://auctions.yahoo.com/
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list