Breadth-first search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

Pseudocode

Input: A graph G and a starting vertex v of G

Output: All vertices reachable from v labeled as explored.

A non-recursive implementation of breadth-first search:

Breadth-First-Search(G, v):

    for each node n in G:           

        n.distance = INFINITY       

        n.parent = NIL

    create empty queue Q     

    v.distance = 0

    Q.enqueue(v)                     

    while Q is not empty:       

    

        u = Q.dequeue()

    

        for each node n that is adjacent to u:

            if n.distance == INFINITY:

                n.distance = u.distance + 1

                n.parent = u

                Q.enqueue(n)