Summary: We can name it (a variant of) preorder children-together depth-first traversal. No particular name or usage for this search algorithm has been found in existing literature yet.
The words "search" and "traversal" are often used interchangeably. In strict sense, this is a traversal algorithm but not a search algorithm (binary search algorithm is a proper search algorithm) since it is not actually searching for any element. Any traversal algorithm can be used for searching naturally, though, which is why we see depth-first search and breadth-first search often.
Description of this algorithm
Firstly, it visits a parent before its children and, hence, before all its descendants)
This property can be considered as the naturalness of a tree traversal algorithm since a parent comes before its children conceptually and historically. Or we can reuse the more conventional term, "preorder" to describe it.
Secondly, it visits children together, but not grandchildren together in general.
Given any node, once it starts traversing its children, it will visit all of its children before any of its further descendants such as grandchildren, great-grandchildren, etc. In other words, all children of any given node will be visited consecutively, in some order which can be specified as, for example, from left child to right child (or some random order).
Thirdly, it is mostly depth-first. After visiting any node, it visits all of its descendants together.
Given any node, once this algorithm begins visiting any of its descendants, it will visit all of its descendants before visiting any node that is not its descendant. It goes deeper and deeper down the descendants towards the leaves, until it reaches the leaves, at which time it will backtrack.
Fourthly, it is not the standard depth-first traversal (SDFS).
For any two siblings nodes $s_1$ and $s_2$, if SDFS visits $s_1$ before $s_2$, then it visits all descendants of $s_1$ before all descendant of $s_2$ as well as $s_2$ itself. In others words, for any two disjoint subtrees $t_1$ and $t_2$, SDFS will either visit $t_1$ completely before $t_2$ or visit $t_2$ completely before $t_1$. However, for this traversal algorithm, if it visit $s_1$ before $s_2$, then it will visit all descendants of $s_1$ after it has visited the subtree at $s_2$.
This fourth point is also implied by the second point.
So this algorithm can be called a variant of preorder children-together depth-first traversal.
Why do we say "a variant of"?
The following algorithm is the algorithm that should be called the preorder children-together depth-first traversal, as it is more natural in the sense that all immediate or distant siblings are visited from left to right, in the same order as children of the same node is visited. In other words, all nodes in the same level are visited from left to right, although not consecutively in general.
myStack = [root] // myStack is a stack.
node = myStack.pop()
for child in node.children: // assuming left to right
for child in node.children.reverse: // pushing children in reverse order
The output of above algorithm on the graph in the question is
F B G A D C E I H
Note that nodes in each level is always visited left to right as [F], [B,G], [A,D,I] and [C, E, H]. This algorithm is also more natural in the sense that can be defined recursively naturally as the following pseudocode in Python style
def traversal(tree, node):
for child in tree.getChildren(node):
for child in tree.getChildren(node):
To traverse a tree T rooted at R, call it as
visit(R); traversal(T, R).
We can generalize this algorithm so that all $k$-level descendants are visited together. For example, we can have a preorder grandchildren-together depth-first traversal, which may output
F B G A D I C E H for the given graph. There are several variations to them, which will not be discussion here.
Tree or general graph
Please note all search strategies mentioned above and in the question can be adapted slightly so as to be applied to general undirected graphs instead of rooted trees. All we need are the following changes. (More adaptation is needed for general directed graphs.)
- Select an arbitrary node as the root.
- Initialize a boolean array to record whether a node has been visited or not.
- Mark a node as visited right after it has been visited.
- Skip pushing any visited node to the stack or queue.
Two simple exercises
Exercise 1. Write the algorithm in the question as a recursive function/method in pseudocode or your favorite language.
Exercise 2. Suppose every parent should be visited after all its descendants. Implement that variation in pseudocode or your favorite language. Show its output for the given graph.