Back
Close

Definition

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors. Thus closer nodes get visited first.

Pseudo-code:

 1    Breadth-First-Search(Graph, root):
 2 
 3     for each node n in Graph:            
 4        n.distance = INFINITY        
 5        n.parent = NIL
 6 
 7     create empty queue Q      
 8 
 9    root.distance = 0
10   Q.enqueue(root)                      
11 
12   while Q is not empty:        
13     
14       current = Q.dequeue()
15     
16       for each node n that is adjacent to current:
17           if n.distance == INFINITY:
18               n.distance = current.distance + 1
19               n.parent = current
20              Q.enqueue(n)

Source: Wikipedia (license)

External resources

Breadth First Search