Knowledge Guide
Home › DSA

Graphs

Step 13 in the DSA path · 10 concepts · 12 problems

0 / 22 complete

📘 Learn Graphs from zero

Graphs — Multi-Source BFS. A graph is just nodes connected by edges; a 2D grid is a graph in disguise where each cell is a node wired to its 4 neighbors. BFS explores outward in concentric rings: it processes every node at distance d before touching distance d+1. The trigger to reach for BFS: you need the shortest distance / minimum number of steps in an unweighted graph, or you must spread something simultaneously from many starting points. The "multi-source" twist is to seed the queue with all starting nodes at once, so the BFS rings emanate from every source together — perfect for "how long until everything is reached?" Canonical problem: Rotting Oranges (LeetCode 994) — a grid where 2=rotten, 1=fresh, 0=empty; each minute every rotten orange rots its 4-directional fresh neighbors. Return minutes until none are fresh, or -1 if impossible.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Seed all sources & count fresh
grid (2=rotten, 1=fresh, 0=empty)
      c0  c1  c2
 r0 [  2   1   1 ]   <- (0,0) is rotten
 r1 [  1   1   0 ]
 r2 [  0   1   1 ]

Scan whole grid once:
  queue = [ (0,0) ]      # ALL rotten cells (sources)
  fresh = 6             # count of every 1
  minutes = 0

We sweep the grid once to push every rotten orange into the queue as a level-0 source, and tally fresh = 6. Seeding all sources together is what makes this multi-source BFS — all rot fronts advance in lockstep, so one shared ring counter equals elapsed minutes.

Step 2 — Process minute 1 (drain the level)
Snapshot queue at start of minute = [ (0,0) ]
Process exactly len(queue)=1 node, rot its fresh nbrs:
  (0,0) -> down (1,0)=1 -> rot;  right (0,1)=1 -> rot
           (up & left are out of bounds)

      c0  c1  c2
 r0 [  2  *2*  1 ]
 r1 [ *2*  1   0 ]
 r2 [  0   1   1 ]

minutes = 1   fresh = 6-2 = 4
queue = [ (1,0), (0,1) ]   # next ring

We freeze the level size (len(queue)) and pop exactly that many nodes, so newly-added cells wait for the next minute. This level-barrier is why BFS measures distance correctly: everything popped this round is exactly 1 step from a source.

Step 3 — Process minute 2
Snapshot queue = [ (1,0), (0,1) ]   (process 2)
  (1,0): up (0,0)=2 skip, down (2,0)=0 skip, right (1,1)=1 -> rot
  (0,1): right (0,2)=1 -> rot;  down (1,1) now 2, skip;  left (0,0)=2 skip

      c0  c1  c2
 r0 [  2   2  *2* ]
 r1 [  2  *2*  0 ]
 r2 [  0   1   1 ]

minutes = 2   fresh = 4-2 = 2
queue = [ (1,1), (0,2) ]

Each neighbor is rotted once: the instant we flip a 1 to 2 it stops being fresh, so it can never be enqueued twice. Mutating the grid in place doubles as the visited set — no separate seen-structure needed.

Step 4 — Process minute 3
Snapshot queue = [ (1,1), (0,2) ]   (process 2)
  (1,1): down (2,1)=1 -> rot;  up/left already 2, right (1,2)=0 skip
  (0,2): down (1,2)=0 skip;  left (0,1)=2 skip

      c0  c1  c2
 r0 [  2   2   2 ]
 r1 [  2   2   0 ]
 r2 [  0  *2*  1 ]

minutes = 3   fresh = 2-1 = 1
queue = [ (2,1) ]

Only one new cell rots this ring; (0,2) contributes nothing because all its in-bounds neighbors are already rotten or empty. The frontier naturally shrinks as the spread runs out of fresh cells to reach.

Step 5 — Process minute 4 (last fresh falls)
Snapshot queue = [ (2,1) ]   (process 1)
  (2,1): right (2,2)=1 -> rot;  up (1,1)=2 skip;  left (2,0)=0 skip

      c0  c1  c2
 r0 [  2   2   2 ]
 r1 [  2   2   0 ]
 r2 [  0   2  *2* ]

minutes = 4   fresh = 1-1 = 0   <- all rotten!
queue = [ (2,2) ]

The final fresh orange at (2,2) flips, driving fresh to 0. The loop condition while queue and fresh will now exit because fresh==0 — we never waste a minute draining the leftover queue.

Step 6 — Terminate & return the answer
Loop guard: while queue and fresh:
   fresh == 0  -> STOP

Final check:
   if fresh == 0:  return minutes   # = 4
   else:           return -1        # unreachable fresh exist

ANSWER = 4

Because BFS expands one ring per minute, the ring counter minutes equals the shortest time for rot to reach the last orange — exactly the minimum we want. The fresh counter is the correctness guard: had any fresh orange been walled off by 0s, fresh would stay positive and we'd correctly return -1. Total work is O(R·C) — each cell is enqueued and visited at most once.

🎯 Guided practice

  1. EASY — Find if Path Exists in Graph. You're given n nodes (0..n-1), a list of undirected edges, a source, and a destination. Return true if a path exists.

    Step 1 — recognize the pattern. Keywords "path exists" + "reachable" with no weights = plain reachability -> DFS or BFS, no shortest-path machinery needed. First handle the trivial edge case: if source == destination, return true immediately (a zero-length path always exists, even on an isolated node).

    Step 2 — build the adjacency list. Iterate the edges; for each [u,v] append v to adj[u] and u to adj[v] (undirected, so both directions).

    Step 3 — traverse from source. Use a stack (DFS) or queue (BFS) and a visited set seeded with source. Pop a node; if it equals destination, return true. Otherwise, for each neighbor not yet visited, mark it visited the moment you push it (not when you pop it) so it can't be enqueued twice.

    Step 4 — terminate. If the structure empties without hitting destination, return false. Complexity: O(V+E) time, O(V) space. Lesson: the visited set is what makes this safe on cyclic graphs and bounds the work to linear. (For the related "minimum edges" or shortest-path variant you'd specifically want BFS; for mere existence either order works.)

  2. MEDIUM — Number of Provinces. Given an n×n matrix isConnected where isConnected[i][j]==1 means city i and j are directly connected, count the number of connected components (provinces). The matrix is symmetric (undirected) with a 1-diagonal.

    Step 1 — recognize the pattern. "Group things that are transitively connected and count the groups" is the textbook connected-components problem. Two standard tools: traverse-and-count (DFS/BFS) or Union-Find. We'll use DFS.

    Step 2 — handle disconnection explicitly. A single DFS only covers one component, so loop i from 0..n-1. Each time you find a city not yet visited, that's a brand-new province -> increment a counter, then DFS to mark its whole component visited.

    Step 3 — the DFS. From city i, scan row i; for every j with isConnected[i][j]==1 and j unvisited, mark j visited and recurse into j. This floods the entire component so it's counted exactly once.

    Step 4 — answer. The counter equals the number of provinces. Complexity: O(n^2) time (you scan every one of the n^2 matrix entries — the matrix IS the edge set), O(n) space for visited + recursion stack. Lesson: "count components" = "for each unvisited node, +1 and flood-fill its reachable set" — the same skeleton powers Rotting Oranges (multi-source BFS over a grid) and Clone Graph (DFS that copies each node once, keyed by an original->copy map that doubles as the visited set).

✨ Added by the guide — work these before the full problem set.

Lessons in this topic