Algorithm for "balanced" breadth-first search

Question

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 (infinitely) many nodes then a pure breadth-first strategy would never reach K, whereas the "balanced" algorithm would still reach K after H but before the other children of E.

_{(The reader who does not like can attain a similar effect with a large but still finite number such as "the greatest number of steps any practical search algorithm will ever make, plus 1".)}

I can only imagine that this style of search or something like it must have been the subject of much research and practical application. I would be grateful to be pointed in the right direction. Thank you.

You'll have to specify exactly what the logic behind "balanced" is, so it is clear what you would need to be the order in *all* scenarios. — trincot, Oct 07 '22 at 08:55

score 2 · Accepted Answer · answered Oct 07 '22 at 09:12

Transform your tree to a different kind of representation. In this new representation, each node has at most two links: one to its leftmost child, and one to its right sibling.

     A
   /   \
  B     C
 /     /  \
D     E    F
|    /|\    \
G   HIJ...   K

⇓

     A
   /  
  B --> C
 /     /  
D     E -> F
|    /      \
G   /        K
   /
  H -> I -> J -> ...

Then treat this representation as a normal binary tree, and traverse it breadth-first. It may have an infinite height, but like with any binary tree, the width at any particular level is finite.

score 0 · Answer 2 · answered Oct 07 '22 at 08:52

depth-first-search, breadth-first-search, A*-search (and others) only differ in how you handle the list of "nodes still to visit".
(I assume you always process the node at the start of the list next)

depth-first-search: append new nodes at the front of the list
breadth-first-search: add new nodes to the end of the list
A*-search: insert new nodes in the list according to costs+heuristic

So you need to formalize how to insert new nodes to the list to fulfill your requirements.

Algorithm for "balanced" breadth-first search

2 Answers2