CMD Guide
Home › DSA

Graphs

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

0 / 23 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

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What is the difference between DFS and BFS in how they explore a graph, and what data structure backs each?
tap to reveal →
DFS explores as far as possible along each branch before backtracking, using a stack (or recursion). BFS explores all neighbors of a node before going deeper, visiting nodes level by level, using a queue.
💡 DFS = dive deep with a Stack; BFS = ripple wide with a Queue.
Flashcard
When should you reach for BFS, and what is the 'multi-source' twist?
tap to reveal →
Use BFS when you need the shortest distance / minimum number of steps in an unweighted graph, or to spread something from many starts at once. Multi-source BFS seeds the queue with ALL starting nodes at level 0 so the rings emanate from every source together (e.g. Rotting Oranges).
💡 Shortest unweighted steps -> BFS. Many starts at once -> seed them all at level 0.
Flashcard
Adjacency matrix vs adjacency list: structure and when each is better?
tap to reveal →
An adjacency matrix is an N x N 2D array where cell (i,j)=1 marks an edge i->j (symmetric for undirected graphs). An adjacency list stores each vertex with a list of its neighbors and is space-efficient for sparse graphs (few edges).
💡 Matrix = N x N grid (dense); List = neighbor lists (sparse).
Flashcard
How do you detect whether all courses can be finished in Course Schedule, and what graph technique applies?
tap to reveal →
Model courses as nodes and prerequisites as directed edges, then check for a cycle. Use Kahn's topological sort: build inDegree + adjacency list, queue all inDegree-0 courses, and on dequeue decrement neighbors' inDegree. If completedCourses == numCourses there is no cycle, so return true.
💡 Can finish all courses == no cycle == topological sort consumes every node.
Flashcard
Which technique counts the Number of Provinces (connected components), and what are its two core operations?
tap to reveal →
Use Union-Find (Disjoint Set) with parent and rank arrays. Each city starts as its own set; for every isConnected[i][j]==1 with different roots, union them and decrement the province count. The Find operation returns a set's representative; the answer is the number of distinct sets.
💡 Provinces = connected components -> Union-Find: Find the root, Union the connected.
Flashcard
How does Find the Town Judge avoid building an explicit graph, and what trust score identifies the judge?
tap to reveal →
Track a single trustScores array (in/out degree net). For each pair [a,b], do trustScores[a]-- and trustScores[b]++. The judge is the person whose score equals n-1 (trusted by all n-1 others, trusts nobody); otherwise return -1. Runs in linear time.
💡 Judge score = n-1: +1 for each truster, -1 for each time you trust.
Flashcard
Why is BFS the right tool for Word Ladder and Bus Routes, and what defines an 'edge' in each?
tap to reveal →
Both ask for a minimum count over an unweighted graph, so BFS finds the shortest path first. In Word Ladder an edge connects two words differing by a single letter; in Bus Routes you map each stop to the buses serving it, and edges let you switch buses at any shared stop, counting bus transfers level by level.
💡 Min hops in unweighted graph -> BFS. Word Ladder: 1-letter swaps. Bus Routes: shared stops = transfers.
Q1. You must return the minimum number of minutes for rot to spread from every rotten orange to all fresh oranges in a grid. Which approach fits best?
Q2. In the Course Schedule topological-sort solution, what does it mean if completedCourses is LESS than numCourses after the queue empties?
Q3. For Clone Graph (deep copy of a connected undirected graph), why is a hashmap essential during DFS?
Q4. In an adjacency matrix for an UNDIRECTED graph with an edge between vertices i and j, which entries are set to 1?
Q5. Which problem is best solved with Union-Find rather than a BFS/DFS shortest-path traversal?