Re: Depth First Search traversal of this list

PJB>>> The confusion is between a "search" and a "walk".
??>>
??>> what is "walk" and how is it different from normal dfs traversal?

GN> A walk touches every node of the tree, a search partitions the tree to
GN> avoid touching every node.

partitions??
do you mean it exists as soon as it finds something, while "walk"
visits all node?

this actually makes sense, but people historically(?) refer to it as dfs
even if they are not going to find anything.

for example, NISTS's "Dictionary of Algorithms and Data Structures"
only has an entry for depth-first-search (no depth first walk or whatever):
----
(1) Any search algorithm that considers outgoing edges (children) of a
vertex before any of the vertex's siblings, that is, outgoing edges of the
vertex's predecessor in the search. Extremes are searched first. This is
easily implemented with recursion. (2) An algorithm that marks all vertices
in a directed graph in the order they are discovered and finished,
partitioning the graph into a forest.

Specialization (... is a kind of me.)
preorder traversal, in-order traversal, postorder traversal.

Note: Depth-first search doesn't specify if a vertex is considered before,
during, or after its outgoing edges or children. Thus it can be preorder,
in-order, or postorder traversal.
----

note that specializations are called traversals rather than searches -- i
guess that's later, more precies terminology comparing to original term dfs.
and it's used like that almost everywhere. in wikipedia:

http://en.wikipedia.org/wiki/Depth-first_search
Depth-first search (DFS) is an algorithm for traversing or searching a tree,
tree structure, or graph.

http://en.wikipedia.org/wiki/Topological_sorting
An alternative algorithm for topological sorting is based on depth-first
search. Loop through the vertices of the graph, in any order, initiating a
depth-first search for any vertex that has not already been visited by a
previous search. The desired topological sorting is the reverse postorder of
these searches.

Boost C++ libraries:
The depth_first_search() function performs a depth-first traversal of the
vertices in a directed graph.

also note, wherever they do not use word "search", they use word
"traversal".
so it seems like "walk" is unofficial rarely-used term (try google searches
for depth-first search, traversal and walk, and see the difference), but
Pascal used it as if everybody
should know what "walk" is and how is it different from search.


.

Relevant Pages

  • Re: Depth First Search in Binary Search Tree?
    ... called "dfs" is beyond me. ... That's not the meaning of a depth-first search. ... This method means that you'll get all the way to the bottom of the tree down ... While a tree is a graph, and therefore can have DFS applied to it, it ...
    (comp.programming)
  • Re: Depth First Search in Binary Search Tree?
    ... then checking the ENTIRE subtree of one of the ... one path before moving sideways at all. ... You keep using the term 'tree'. ... specific depth had something to do with it being a depth-first search. ...
    (comp.programming)
  • Irregularity In Definition Binary Tree Depth
    ... I've noticed that almost all computer science books define the depth of ... a binary tree as the number of links that must be traversed from the ... Defined as such, the depth of a single-node tree becomes 1, not 0, as ... (Count the pointer traversals, not the nodes). ...
    (comp.theory)
  • Re: q: point quadtree speed
    ... > simply an unavoidable cost. ... plain buggy implementation. ... pointer traversals at an already excessive design size of 1 leaf/entry ... How deep did you make the tree? ...
    (comp.graphics.algorithms)
  • Re: help: a O(n) algorithm to find the longest path in a tree
    ... An faster alternative to your depth-first search of the tree might be ... to mark the nodes of a tree with depth data; ...
    (comp.theory)