Day 31 · Friendship maps, ripples & corridors

Graphs, BFS & DFS

You will be able to

Represent a graph as an adjacency list and say when a matrix wins instead
Implement BFS with a queue and use it for shortest unweighted paths
Implement DFS both recursively and with an explicit stack
Detect cycles and count connected components
Explain topological sort and where it applies (DAGs only)

Today's ~120 minutes

Spaced-rep warm-up: due cards (heaps, trees, queues)	10 min
ELI5 + tech read; run BFS in the visualizer and watch the rings	18 min
Guided: BFS shortest path, islands, cycle detection	42 min
Practice: rotting oranges (multi-source BFS)	20 min
Project: graph toolkit + import-dependency mapper	20 min
Quiz + flashcards	10 min

Builds on: Day 25 — Stacks & queues · Day 27 — Recursion & divide/conquer · Day 29 — Binary trees & BSTs

The analogy

🧸 ELI5⚙ Tech

A friendship map: dots for people, lines for "knows each other." No root, no up or down, no rule about two children — just things and connections. That is a graph, and it is the most general shape data takes: cities and roads, packages and dependencies, web pages and links, tasks and prerequisites.

Two ways to explore it. BFS is a ripple: drop a stone at your starting person and the wave reaches all their friends first, then friends-of-friends, then friends-of-friends-of-friends. Because the ripple expands one ring at a time, the first time it touches someone is provably the SHORTEST path to them — that is BFS's superpower. DFS is exploring corridors: pick a hallway, follow it to the very end, back up to the last junction, try the next hallway. You do not find shortest paths this way, but you thoroughly map every reachable room — perfect for "is there any path?", "does this maze loop back on itself?", and "which rooms form one connected building?" One structure decides everything: a queue makes the ripple, a stack (or recursion — the call stack) makes the corridor-crawl.

Why this matters on the job

Graphs are the interview category that separates prepared candidates, and they saturate real AI work: dependency resolution in build systems and package managers is topological sort; a multi-step agent's tool-call plan (Day 121) is a DAG; knowledge-graph RAG (Day 118) retrieves by walking edges; crawl-and-ingest pipelines for RAG corpora are literally BFS over hyperlinks. When your Day 148 Docker builds order their layers or your Day 152 CI pipeline orders its jobs, a topological sort ran. "Model the mess as nodes and edges, then BFS/DFS it" is a career-long move.

Watch it happen

The ripple — BFS explores in rings from A

step 1 / 6

A friendship map. BFS explores like a ripple: everyone 1 hop away, THEN everyone 2 hops away. A queue enforces the order — first discovered, first explored.queue: [A]

🎯 Predict modespeed1×

Guided practice

guided 1

Adjacency list + BFS shortest path

20 min

Create graphs_lab.py. Build the starter's small undirected graph as a dict-of-sets adjacency list.
Implement bfs_distances(graph, start) returning a dict node → distance. Discipline: mark visited when ENQUEUEING. Predict the distances from "a" on paper first.
Extend it to shortest_path(graph, start, goal) by also recording each node's parent when discovered, then walking parents backwards from the goal. Verify the path found for a → f is one of the shortest ones.
Break it on purpose: move the visited-marking to pop time on a graph with a cycle and print the queue's length over time. Watch the duplicate explosion — now you will never make that mistake under interview pressure.

🐍 python — editable, runs in your browser

from collections import deque

graph = {
    "a": {"b", "c"},
    "b": {"a", "d"},
    "c": {"a", "d", "e"},
    "d": {"b", "c", "f"},
    "e": {"c", "f"},
    "f": {"d", "e"},
}

def bfs_distances(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in dist:          # 'in dist' doubles as the visited set
                dist[nb] = dist[node] + 1
                q.append(nb)            # marked at enqueue time
    return dist

def shortest_path(graph, start, goal):
    parent = {start: None}
    q = deque([start])
    while q:
        node = q.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nb in graph[node]:
            if nb not in parent:
                parent[nb] = node
                q.append(nb)
    return None                          # unreachable

print(bfs_distances(graph, "a"))   # a:0 b:1 c:1 d:2 e:2 f:3
print(shortest_path(graph, "a", "f"))

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Number of Islands + cycle detection, think-aloud

22 min

Classic 1 — Number of islands. Think aloud: "The grid IS a graph — cells are nodes, 4-neighbors are edges. Each island is a connected component. Scan every cell; when I hit unvisited land, that is a NEW island: count it and flood-fill (DFS) the whole component so I never count it again." Implement count_islands with the starter grid; use an explicit stack so a huge grid cannot overflow recursion.
Trace your flood fill on the 3-island starter grid by hand for the first island — list the cells in the order visited.
Classic 2 — Course Schedule. Think aloud: "Courses and prerequisites form a directed graph. I can finish all courses if and only if there is no cycle." Implement can_finish with DFS three-state coloring: unvisited / on-current-path / done. Revisiting an on-path node = cycle.
Test with a cyclic prerequisite pair (A needs B, B needs A) and a valid chain. Then say the connection: three-state DFS and Kahn's algorithm are two roads to the same theorem — topological order exists iff no cycle.

🐍 python — editable, runs in your browser

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    def flood(r, c):
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            if (cr, cc) in seen:
                continue
            seen.add((cr, cc))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = cr + dr, cc + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == "1" and (nr, nc) not in seen):
                    stack.append((nr, nc))
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                flood(r, c)
    return count

grid = [list("11000"), list("11000"), list("00100"), list("00011")]
print(count_islands(grid))   # 3

def can_finish(num_courses, prereqs):
    graph = {i: [] for i in range(num_courses)}
    for course, needs in prereqs:
        graph[needs].append(course)
    state = {}                    # missing=unvisited, 1=on path, 2=done
    def has_cycle(node):
        state[node] = 1
        for nb in graph[node]:
            s = state.get(nb, 0)
            if s == 1:            # back to a node on the current path
                return True
            if s == 0 and has_cycle(nb):
                return True
        state[node] = 2
        return False
    return not any(state.get(n, 0) == 0 and has_cycle(n) for n in graph)

print(can_finish(2, [(1, 0)]))          # True
print(can_finish(2, [(1, 0), (0, 1)]))  # False -- cycle

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Rotting oranges (multi-source BFS)

20 min

A grid holds fresh oranges (1), rotten oranges (2), and empty cells (0). Every minute, rot spreads to 4-adjacent fresh oranges. Return the minutes until no fresh orange remains, or -1 if some orange can never rot.

Solve with BFS. The twist to discover: the ripple starts from ALL rotten oranges at once. Test on a grid where two rot sources race toward the same fresh orange, and on a grid with an unreachable orange.

Hints: seed the queue with every rotten cell (all at distance 0) before looping — multi-source BFS is ordinary BFS with a bigger starting ring. Count remaining fresh oranges to detect the -1 case.

Ship before you stop

Graph toolkit + the import-dependency mapper

Two deliverables in dsa/graphs.py. First: today's core — bfs_distances, shortest_path, count_islands, can_finish — with pytest cases including a disconnected graph and a self-loop. Second, the fun one: import_graph(directory) walks your practice repo's Python files (pathlib from Day 5), regex-extracts local import statements (Day 13), builds a directed graph of module dependencies, and prints a topological order — or names the cycle if one exists. Run it on your own repo and commit the output in the docstring.

Rubric — check what you completed (0/5)

BFS shortest path verified against a hand-computed answer on a 6+ node graphcount_islands handles all-water, all-land, and diagonal-only grids (diagonals are NOT connected)can_finish detects a 3-node cycle and passes a valid DAGImport mapper produces a valid topological order on your real repo (every edge points forward)Tests green; committed with a descriptive message

Common mistakes & misconceptions

Marking nodes visited at POP time instead of enqueue time — the queue floods with duplicates and BFS silently goes superlinear. Mark when enqueueing.
Using DFS for shortest path. DFS finds A path, not the shortest; only BFS guarantees minimal edges in unweighted graphs.
Forgetting the visited set entirely on cyclic graphs — infinite loop. Trees forgive this (no cycles); graphs never do.
Recursion-depth crashes on big grids: a 1000×1000 grid can recurse a million deep. Know the iterative-stack DFS.
Detecting directed cycles with a plain visited set. A visited node reached again via a DIFFERENT path is not a cycle — you need the "on current path" state.
Trying to topologically sort a cyclic graph. Topo order exists only for DAGs; the algorithm failing IS your cycle detector.

Knowledge check

Q1. Why does BFS — and not DFS — find shortest paths in unweighted graphs?

Q2. In BFS, when should a node be marked visited?

Q3. Course A requires B, B requires C, C requires A. What does topological sort do here?

Go deeper — curated resources

toolVisuAlgo — Graph traversal (DFS/BFS) visualization ↗15 min bookOpenDSA — Graphs chapter ↗25 min courseNeetCode Roadmap — Graphs section ↗15 min

If you have a third hour

Dijkstra = BFS + a priority queue — Swap the BFS queue for Day 30's min-heap keyed by path cost and you get Dijkstra's algorithm for weighted graphs. Sketch the change on paper — it is a 5-line diff.

Done means

BFS marks visited at enqueue; duplicate-explosion experiment observed and explained
Number of islands and course schedule pass tests including edge cases
Rotting oranges handles the unreachable-orange case (-1)
Import-dependency mapper runs on your real repo; toolkit committed
Quiz ≥ 2/3

How this connects

← Back: BFS is Day 25's queue plus Day 29's level-order, generalized; DFS is Day 27's recursion with a visited set because graphs, unlike trees, can loop. The adjacency list is Day 23's dict-of-sets.

Forward →: Day 34's DP problems are often shortest paths on implicit DAGs. Day 118's graph-RAG retrieves by edge-walking, Day 121's agent plans are DAGs your topo-sort intuition will read, and Day 148's Docker layer graph and Day 152's CI job ordering are topological sorts in production clothing.

Unlocks: D35 Week 5 Checkpoint: Interview Drill I