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
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants