Breadth-first search

In computer science, breadth-first search (BFS) is a method used for traversing a graph. It starts at any item you want to use as a starting position in a graph, and explores all of the neighbor items at the present depth before to moving on to the items at the next depth level. A breadth-first search done on a tree (data structure) is called a level-order traversal.

Animated example of a breadth-first search (level-order traversal) within a tree.

Implementation

<syntaxhighlight lang="java"> void breadthFirstSearch(Item root) {

   Queue q = new Queue();
   root.found = true;
   q.enqueue(item);
   while (!q.isEmpty()) {
       Item v = q.dequeue();
       for (Item neighbor : v.neighbors()) {
           if (!neighbor.found) {
               neighbor.found = true;
               q.enqueue(neighbor);
           }
       }
   }

} </syntaxhighlight>

Usage

Though they have usage in a variety of disciplines, breadth first search algorithms are most often associated with finding the shortest distance between two points, such as on a map.

Breadth-first Search Media

Related pages