DSA Notes

Graphs

BFS

Explore in rings: everything at distance 1, then 2, then 3.

The idea

Breadth-first search keeps a queue of vertices to expand. Because vertices leave the queue in order of distance, the first time a vertex is reached is along a shortest path, counted in edges.

It runs in O(V + E) and is the tool for shortest paths when every edge costs the same, including moves on a grid.

Starting with several sources in the queue at distance 0 gives each vertex its distance to the nearest source in a single pass.

Sample problem

542. 01 Matrix ↗ Medium

Given a grid of 0s and 1s, return for every cell the distance to the nearest 0. Neighbouring cells (up, down, left, right) are at distance 1.

mat = 0 1 1 1      output = 0 1 2 3
      1 1 1 1               1 2 3 2
      1 1 1 1               2 3 2 1
      1 1 1 0               3 2 1 0

Why the solution works

Running a search from every 1 to find its nearest 0 repeats the same work many times. Turn it around: search outwards from the 0s.

Breadth-first search visits cells in order of distance. If all the 0 cells are put in the queue first, at distance 0, the search spreads from them at once, and the first time a cell is reached is from its nearest 0.

The queue is what guarantees the order: everything at distance d leaves it before anything at distance d + 1.

Complexity: O(R · C) time and memory: each cell enters the queue once.

Watch out

  • Set the distance when a vertex is pushed, not when it is popped, or it gets queued many times.
  • BFS is only correct when all edges have equal weight. With weights 0 and 1 use a deque; otherwise Dijkstra.
  • Check grid bounds before reading a cell.
Watch it run

Practise on LeetCode