DSA — Graph Algorithms

BFS Breadth-First Search

Layer-by-layer exploration of graphs. Perfect for finding the shortest path in unweighted graphs.

— min read
O(V+E)Time
O(V)Space
ShortestPath (unwt.)
QueueBFS Uses
LevelOrder
// BFS VISUALIZATION
Initialize to see BFS in action.
How It Works
Python Code
Complexity
Quiz
Practice
01
Start Node
Enqueue the starting node and mark it as visited.
02
Process Queue
Dequeue a node and explore all its immediate unvisited neighbors.
03
Enqueue Layer
Add neighbors to the queue and mark them visited. Repeat until queue is empty.
python 
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
O(V+E)
Time
Each vertex and edge visited once
O(V)
Space
Queue can hold all vertices
FIFO
Queue
First-in-first-out exploration
Shortest
Path
Unweighted graphs only
BFS uses which data structure?
Progress 0 / 4 solved
4 problems · 3 PBC · 1 Startup
#101 Binary Tree Level Order Google, Amazon PBC →
#200 Number of Islands Meta, Amazon PBC →
#994 Rotting Oranges Microsoft PBC →
#127 Word Ladder Zepto STARTUP →
← Graphs