I'm looking for references for an algorithm that conducts a breadth-first tree search in a balanced manner that is resilient in a situation where
- we expect most nodes to have few children, but
- a few nodes may have a many (possibly infinitely many) children.
Consider this simple tree (modified from this post):
A
/ \
B C
/ / \
D E F
| /|\ \
G HIJ... K
Depth-first visits nodes in this order:
A B D G C E H I J ... F K
Breadth-first visits nodes in this order:
A B C D E F G H I J ... K
The balanced breadth-first algorithm that I have in mind would visit nodes in this order:
A B C D E G F H K I J ...
Note how
- we visit G before F, and
- we visit K after H but before I.
G is deeper than F, but it is an only child of B whereas F is a second child of C and must share its search priority with E. Similarly between K and the many children H, I, J, ... of E.
I call this "balanced" because a node with lots of children cannot choke the algorithm. Concretely, if E has