Breadth-first search facts for kids

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

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);
            }
        }
    }
}

Related pages

• Linear search
• Binary search
• Depth-first search
• Bidirectional search

Images for kids

• 

  BFS on Maze-solving algorithm

See also

In Spanish: Búsqueda en anchura para niños