TRT
Sign in

Advanced · Module 13 · Lesson 2 of 5

Breadth-first search

Breadth-first search explores a graph in rings of increasing distance from the start, using a queue and a visited set. In an unweighted graph, the first time it reaches a vertex is along a shortest path.

Pro — members onlyAbout 14 minutes

By the end you can

  • Run breadth-first search with a queue and a visited set, marking vertices when they are enqueued
  • Compute shortest distances and paths in an unweighted graph, and explain why they are shortest
  • Apply BFS to grids, implicit state graphs and multiple starting points

Builds on Representing graphs.

01 · A question first

What is the fewest number of steps from the entrance of a maze to the exit? Exploring in rings of increasing distance answers it, and the first time the search reaches the exit is guaranteed to be by a shortest route. Why does the first visit win?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Rings of increasing distance
  • Mark when you enqueue
  • Why the first visit is the shortest
  • BFS on grids and states
  • Many starting points
  • What it costs in practice
  • Searching from both ends
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeRotting orangesFind how many minutes it takes rot to spread from every rotten orange to all fresh ones, with a multi-source BFS.Practice · hard · LeetCodeWord ladderFind the length of the shortest chain of one-letter changes from one word to another through a dictionary, with BFS over an implicit graph.Practice · medium · LeetCodeShortest path in binary matrixFind the shortest clear path from the top-left to the bottom-right of a grid, moving in eight directions, with BFS.

Asked in interviews

Something wrong with this lesson? Report a problem