Breadth First Search (BFS)

Given a graph as an adjacency list and a starting vertex, return the order of vertices visited using **Breadth First Search**.

Visit neighbors level by level using a queue.

Input: graph = [[1,2],[0,3],[0,3],[1,2]], start = 0

Output: [0,1,2,3]

Visit 0, then its direct neighbors 1 and 2, then 3.

Input: graph = [[1],[0,2],[1]], start = 0

Output: [0,1,2]

Simple chain graph.

Time

O(V + E)

Space

O(V)

queue and visited set.

#1 — Standard graph

Input: graph=[[1,2],[0,3],[0,3],[1,2]] start=0

Expected: [0,1,2,3]

#2 — Chain graph

Input: graph=[[1],[0,2],[1]] start=0

Expected: [0,1,2]

#3 — Isolated vertex

Input: graph=[[],[]] start=0

Expected: [0]

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.