bfs
Breadth First Search (BFS)
Graph traversal method
Uses QUEUE
TIME COMPLEXITY - O(N)
SPACE COMPLEXITY - O(B^D) / O(W)
B is branching factor (max child per node eg. 2), D is depth (max distance from root)
W is width of biggest level
Max space needed in queue
HORIZONTAL then VERTICAL
How?
Starts at some node , explore neighbour nodes , before moving on to next level neighbours ( Explores nodes in layers )
Use FIFO queue to see which nodes is visited first
Application : finding shortest path on unweighted graph
Breadth First Search Implementation in Python
Python code implementation with explanation
Last updated