Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 63 ยท Graphs for Contests

Graph Problems: Modeling and Traversal

Turn contest statements into graphs, run BFS over implicit state graphs, use multi-source BFS and 0-1 BFS, and rebuild the path from parent pointers.

Most graph problems in contests do not say "graph" anywhere. They describe a maze, a puzzle with moves, a set of cities, or a game board, and the hard part is noticing that it is a graph problem at all. Once you see the graph, the algorithm is usually one of a small family: BFS, DFS, shortest paths, or a union-find structure.

This lesson is about the first step, modeling, and about the breadth-first search variants that appear again and again. If BFS itself is new to you, read Graph BFS and Graph Representations first.

From statement to graph

Ask three questions, in this order:

  1. What is a vertex? Whatever you need to remember about the situation: a cell, a person, a pair (position, keys held), a pair of jug volumes. This is called the state.
  2. What is an edge? One legal move or relationship that goes from one state to another.
  3. What is the question? Shortest number of moves (BFS), reachability (BFS or DFS), connected components, or an ordering.
flowchart LR
    A["Statement"] --> B["Define the state"]
    B --> C["List the legal moves"]
    C --> D["Count states: is it small enough?"]
    D --> E["Pick BFS, DFS or Dijkstra"]

The modeling checklist. The state count decides whether the idea is feasible.

The third step in the picture matters most. A graph with 10^6 states and 4 moves each is fine; one with 10^12 states is not, no matter how clever the search. If the state is too big, shrink it by dropping information that does not matter, or look for a different approach.

BFS on implicit graphs

An implicit graph is never stored. You write a function that, given a state, produces its neighbors. You only keep a dist dictionary (or array) for states you have reached. Plain BFS then finds the minimum number of moves whenever every move costs the same.

A classic example is the two-jug puzzle. You have jugs of capacity A and B liters and unlimited water. A move fills a jug, empties a jug, or pours one into the other until the source is empty or the target is full. What is the fewest moves to get exactly T liters in either jug? The state is (a, b), so there are at most (A + 1)(B + 1) states.

To print the actual moves, store a parent for each state, then walk back from the goal.

Python BFS on an implicit state graph: two jugs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the shape: a queue, a parent dictionary that doubles as the visited set, and one check if nxt not in parent. Nearly every BFS solution in a contest is a variation of these ten lines. Mark a state visited when you push it, not when you pop it, otherwise the same state can enter the queue many times.

Multi-source BFS

Sometimes a question asks for the distance from each cell to the nearest of many special cells: distance to the closest fire, closest exit, closest zero. Running one BFS per source is too slow. Instead, put all sources in the queue at distance 0 and run one BFS. The first time a cell is reached, it is reached from its nearest source, because BFS explores by increasing distance.

You can picture it as adding a hidden super-source connected to every real source by an edge of weight 0.

Python Distance to the nearest 1 in a grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same idea solves "spreading" problems: fire and a runner (BFS the fire first, then BFS the runner and only enter cells reached by the fire later), or infection that spreads one step per minute.

0-1 BFS

What if moves have different costs, but only 0 or 1? Dijkstra would work, but there is a simpler and faster tool. 0-1 BFS uses a deque:

  • When you relax an edge of weight 0, push the neighbor on the front.
  • When you relax an edge of weight 1, push the neighbor on the back.

The deque always holds vertices in nondecreasing distance order, with at most two distinct distance values at once, so each vertex is finalized the first time it is popped (and a vertex can be pushed again if you later find a shorter route, so use the usual if new < dist test).

A typical statement: a grid of . (free) and # (wall). You may walk onto free cells at no cost, and you may break a wall at cost 1. What is the minimum number of walls to break to get from the top left to the bottom right?

Python 0-1 BFS: fewest walls to break

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

More general than grids: if a problem lets you pay 0 to follow an edge in its direction and 1 to follow it backwards, "orient the graph with the fewest flips" is also 0-1 BFS. Add each edge forward with weight 0 and backward with weight 1.

State-expanded BFS

When the same cell can be visited in different conditions, the condition becomes part of the vertex. Examples: (cell, keys_collected), (cell, direction), (cell, walls_broken_so_far), (cell, time mod 3). The BFS code does not change; only the tuple does. The number of states multiplies, so check that the product stays within limits. The next lesson, Shortest Paths in Practice, uses the same idea with weighted edges.

Common traps

  • Visited too late. Marking on pop instead of on push makes BFS slow and sometimes memory-hungry.
  • Wrong start distance. If the start cell itself is a wall in a 0-1 problem, it may already cost 1.
  • Using a list as a queue. list.pop(0) is O(n); use collections.deque.
  • Recursive DFS on deep graphs. A path of 10^5 vertices overflows the recursion stack; use an explicit stack or BFS. See DSU and Tree Problems for iterative traversal.
  • Forgetting disconnected graphs. Loop over all start vertices when counting components.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the jug puzzle, what is a vertex of the graph?

    A vertex is the full state of the situation. Moves are the edges between states.
  2. 2. Why does multi-source BFS give the distance to the nearest source?

    With all sources enqueued at distance 0, a cell is first reached by the source closest to it, so one BFS replaces many.
  3. 3. In 0-1 BFS, where is a neighbor pushed after a relaxation with an edge of weight 0?

    A zero-cost edge keeps the same distance, so the neighbor belongs with the current smallest distances at the front. Weight-1 neighbors go to the back.
  4. 4. A maze lets you walk through at most k walls. What should the BFS state be?

    Reaching a cell having broken 0 walls is better than reaching it having broken 3, so they are different states.

Summary

  • Define the state, list the legal moves, count the states, then choose the algorithm.
  • BFS on an implicit graph needs a neighbor function, a queue, and a visited map; store parents to rebuild the path.
  • Multi-source BFS starts with every source in the queue at distance 0.
  • 0-1 BFS uses a deque: weight-0 edges go to the front, weight-1 edges to the back.
  • Extra information that changes what moves are possible becomes part of the state.
  • Mark visited on push, use deque, and avoid deep recursion.

Next: Shortest Paths in Practice