BFS [mp]

Micro pattern¶

Description¶

Explore states level by level so the first visit reaches a state through the fewest unweighted edges.

Problems¶

Graph BFS¶

Mark states on discovery to avoid repeated insertion into the queue.

• BFS (DSA)
• 207. Course Schedule (Top Hard)
• 210. Course Schedule II (Top Hard)
• 802. Find Eventual Safe States (Graph Theory)
• 1129. Shortest Path with Alternating Colors (Graph Theory)
• 1926. Nearest Exit from Entrance in Maze (Graph Theory)
• 433. Minimum Genetic Mutation (Graph Theory)
• 1091. Shortest Path in Binary Matrix (Graph Theory)
• 863. All Nodes Distance K in Binary Tree (Graph Theory)
• 864. Shortest Path to Get All Keys (Graph Theory)
• 1203. Sort Items by Groups Respecting Dependencies (Graph Theory)
• 1857. Largest Color Value in a Directed Graph (Graph Theory)

Tree levels¶

Freeze the current queue length to process one tree level at a time.

• 102. Binary Tree Level Order Traversal (Top Easy)
• 104. Maximum Depth of Binary Tree (Top Easy)
• 103. Binary Tree Zigzag Level Order Traversal (Top Medium)
• 863. All Nodes Distance K in Binary Tree (Graph Theory)

Multi-source BFS¶

Seed the queue with all sources to expand their waves together.

• 542. 01 Matrix (Google Prep)
• 329. Longest Increasing Path in a Matrix (Top Hard)
• 934. Shortest Bridge (Graph Theory)

Bidirectional BFS¶

Expand frontiers from both endpoints to reduce the explored state space.

• 127. Word Ladder (Top Hard)