Home > front end >  Algorithm for "balanced" breadth-first search
Algorithm for "balanced" breadth-first search

Time:10-07

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

  • Related