Graphs — Representation, BFS, DFS, Shortest Path

Review boundary and corrected contracts

BFS gives shortest hop paths; weighted shortest paths need a suitable algorithm, with nonnegative weights for Dijkstra. Corrected −1 parent-sentinel collision and recursive DFS output copying. Connected components assumes an undirected graph; topological sort takes a complete declared vertex set.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Represent graphs three ways, traverse them with BFS / DFS / Dijkstra, and recognise where they secretly show up in every real system (route planners, social networks, dependency resolvers, package managers).

Why this session exists

Many useful problems can be modelled as graphs, but selecting an algorithm still requires an explicit vertex, edge and cost contract. Social networks, road maps, package dependencies, task schedulers, LLM knowledge graphs, git commits, database query planners — graph-shaped examples with different tasks; optimisation, constraint solving and distributed protocols are not reducible to a single BFS/DFS call. This session teaches the three representations, the four canonical algorithms (BFS, DFS, Dijkstra, topological sort), and the patterns that turn ‘this problem is complicated’ into ‘this problem is a graph, and I already know the algorithm’.

You will be able to

• Choose between adjacency list, adjacency matrix, and edge list based on graph density.

• Write BFS for shortest-path-in-unweighted-graph and DFS for connectivity from memory.

• Reuse S029's Dijkstra to solve weighted shortest path.

• Detect a cycle in a directed graph and compute a topological order.

• Recognise real problems (route planning, package resolvers, deadlock detection) as graph traversals.

Prerequisites

• S028 · Trees & BSTs — undirected trees are connected acyclic graphs; disconnected acyclic graphs are forests.
• S029 · Heaps & Priority Queues — used for Dijkstra.
• S026 · Stacks & Queues — BFS is a queue, iterative DFS is a stack.

Pre-read · skim before the session (30 min total)

Further reading: NetworkX Tutorial

Further reading: LeetCode · Graph Explore Card

Further reading: BFS + DFS reference — cp-algorithms

Optional archived videos

These original resource pointers are retained as optional practice aids, not governing evidence for technical claims.

• Graph Algorithms in 100 Seconds — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• Graph Traversals — BFS + DFS · Neetcode — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• Topological Sort · Kahn's Algorithm — archived title/attribution; playback, duration and channel identity not independently verified in this review.

(a) Intuition · 5 min

A graph is a subway map

Real: Stations are nodes. Tracks are edges. Some edges are directed (one-way tunnels), most are undirected (both ways). Some are weighted (this segment takes 4 minutes, that one 12). To go from your stop to a destination, you're asking a graph algorithm: ‘which sequence of edges gets me there — with the fewest stops (BFS) or the shortest time (Dijkstra)?’ Every ride-hailing app, every routing service, every ‘friends of friends’ suggestion — subway-map thinking behind different labels.

 
    A graph G = (V, E) is a set of vertices and edges. Represent it with an adjacency list dict[node → list[neighbor]] and traversal algorithms become 15 lines of Python. BFS explores in expanding rings from the start; DFS goes deep down one path before backtracking. Both visit every reachable node exactly once → O(V + E).
    Nonnegative weighted edges add cost per hop → Dijkstra with a heap. Directed acyclic dependencies permit topological sorting; direction alone is not enough. Cycles add complication → cycle detection with three-colour DFS.
  

Four graph algorithms and their contracts

Choose the guarantee before the template

• BFS — shortest edge-count path in unweighted graphs, level-order exploration.

• DFS — connectivity (‘can I reach A from B?’), cycle detection, topological sort, backtracking searches.

• Dijkstra — shortest path in graphs with non-negative edge weights; travel-time routing is an application model, not a claim about a vendor’s current implementation.

• Topological sort — dependency-ordered traversal of a DAG (build systems, task schedulers, package managers).

Track discovery for these cyclic-graph templates

The reachability BFS/DFS below uses a visited set so a cycle or shared destination is not expanded repeatedly. A child-only rooted tree needs no visited set under its no-sharing/no-cycle contract. An undirected tree stored with both edge directions still needs a parent check or visited set to avoid immediately returning along the same edge. Other algorithms may instead use colours, distance relaxation or path-local cycle checks; not every graph algorithm uses one global visited set.

Timeline — the algorithms that built the modern internet

The conceptual lineage connects Euler's bridge question (edge traversal, not merely vertex reachability), shortest-path optimisation, DFS-based strongly connected components, link-based ranking such as PageRank, social associations and graph databases. These solve different problems: PageRank is an iterative ranking computation; an SCC algorithm needs discovery/finish-state reasoning beyond a plain visited set; graph storage does not choose a recommendation algorithm for you. This is conceptual history, not verification of the inherited coffee anecdote, vendor founding dates or universal adoption claims.

(b) Representation, frontier order, and dependencies · 15 min

The subway analogy leaves two implementation choices open: how to retrieve a station’s neighbours and which discovered station to visit next. Separate those choices before adding the different ordering constraint imposed by task dependencies.

Three representations, one graph

Take A as the starting vertex in this undirected graph. It has neighbours B and D, while E can be reached through B or C. That shared destination is a reason to track discovery rather than assume every new edge leads to a new vertex.

An adjacency list stores A’s two neighbours directly; a matrix records the same edges in A’s row, while an edge list records the pairs. The graph does not change when its storage changes. What changes is the cost of answering “which neighbours can I explore now?”

Name: Adjacency list

Tagline: dict[node] -> list of neighbors

• Space O(V + E) — best for sparse

• Iterate neighbors of u in O(deg(u))

• The default for real code

• Python: dict of sets or lists

Name: Adjacency matrix

Tagline: V × V boolean/int matrix

• Space O(V²) — useful for dense graphs or algorithms that benefit from constant-time edge tests, even when memory is deliberately traded for speed

• O(1) edge-existence check

• O(V) to list neighbors of a node — expensive

• Great for matrix-multiplication algorithms (path counts)

Name: Edge list

Tagline: list of (u, v, weight)

• Space O(E) for edge records, plus an explicit O(V) vertex list if isolated vertices must be retained; not universally the most compact encoding

• No fast neighbor lookup

• Used for Kruskal's MST + I/O

• Good for read-only analysis

Name: NetworkX (Python)

Tagline: A prototyping library

• nx.Graph() / nx.DiGraph()

• Provides graph classes and conversion utilities; representations have distinct semantics and costs

• Includes many standard algorithms; check each API’s graph-type and weight contract

• Great for prototyping

BFS expands in rings; DFS drills deep

With neighbour lookup settled, choose a frontier policy. These sketches show exploration patterns rather than another representation of the labelled graph above: FIFO keeps an entire distance layer ahead of the next, while a stack follows the newest branch.

BFS finishes layer 1 before expanding layer 2, so first discovery gives a shortest hop count in an unweighted graph. DFS can reach depth 3 while a shallower sibling is still waiting; its first route is therefore not a shortest-path certificate.

Topological sort — dependency ordering

Dependencies introduce a different requirement from proximity or reachability. A task is eligible only after its prerequisites have been processed. For a directed acyclic graph, the queue below therefore contains zero-in-degree nodes, not simply every newly discovered neighbour.

Precondition: DAG

Desc: Directed AND acyclic. If there's a cycle, no valid order exists.

Compute in-degrees

Desc: For each node, count incoming edges.

Queue all zero-in-degree nodes

Desc: These have no unmet dependencies — safe to process first.

Pop a node, add to output, decrement each successor's in-degree

Desc: When a successor's in-degree hits 0, enqueue it.

Repeat

Desc: If output size < V at the end, there was a cycle → no valid topo order.

Where these algorithms show up in real systems

Graph algorithms as you'll actually use them

Name: BFS in the wild

Desc: Fewest-hop reachability and bounded friends-of-friends candidate generation. A crawler also needs admission/deduplication policy; ARP address resolution is not a shortest-path algorithm.

Name: DFS in the wild

Desc: ‘Can I reach X’ — connected components, deadlock detection in databases, garbage collector marking, maze solvers.

Name: Dijkstra in the wild

Desc: Minimum-cost paths under a nonnegative additive cost model. OSPF specifies Dijkstra-based shortest-path tree construction; BGP uses path attributes and routing policy, not simply minimum additive edge weight.

Name: Topological sort in the wild

Desc: Order a selected acyclic dependency graph, such as prerequisite tasks. Package version selection additionally solves constraints/backtracks; resource scheduling and parallel execution require more than an ordering.

The universal graph question is ‘what does an edge mean?’

For a routing app it means ‘there's a road between these two intersections’. For a package manager, ‘this package requires that package’. For a social graph, ‘these people are friends’. Then define direction, weight domain, vertex universe and requested output. Those choices distinguish reachability, shortest paths, dependency order and constraint satisfaction.

The edge’s meaning also determines what “shortest” measures. The BFS layers counted edges, not travel time or money; the counterexample below makes that distinction visible before the implementations use both a FIFO queue and a heap.

Myth: "BFS finds the shortest path. So if I need a shortest path, I use BFS."

BFS solves minimum-hop paths. For weighted costs use an algorithm whose assumptions match the weights: nonnegative Dijkstra, DAG relaxation, or Bellman–Ford for negative edges. A reachable negative cycle makes costs unbounded below for destinations reachable from that cycle; other destinations can still have finite distances.

Why: Because the examples are always grids and mazes, where every step costs 1, so "fewest steps" and "shortest distance" coincide and the distinction is invisible. When edge costs vary, fewest edges and cheapest cost can diverge. BFS still answers the hop-count question correctly, but that may not be the objective you intended.

Test: A weighted graph where the fewest-edge path is not the cheapest. This standalone example uses ordered string labels and nonnegative integer weights:

from collections import deque
import heapq
 
W = {'A': [('B', 1), ('C', 10)], 'B': [('C', 1)], 'C': []}
 
def bfs_hops(s, t):
    q, seen = deque([(s, 0)]), {s}
    while q:
        u, hops = q.popleft()
        if u == t:
            return hops
        for v, _ in W.get(u, []):
            if v not in seen:
                seen.add(v)
                q.append((v, hops + 1))
    return None
 
def weighted_distance(s, t):
    heap, settled = [(0, s)], set()
    while heap:
        distance, u = heapq.heappop(heap)
        if u in settled:
            continue
        settled.add(u)
        if u == t:
            return distance
        for v, weight in W.get(u, []):
            if v not in settled:
                heapq.heappush(heap, (distance + weight, v))
    return None
 
assert bfs_hops('A', 'C') == 1
assert weighted_distance('A', 'C') == 2

The single edge costs 10, while the cheapest two-edge route costs 2. The weighted function settles once and stops at the goal; that is safe only with the stated nonnegative weights. Do not extend that guarantee to negative edges.

Question: Why does first-discovery BFS produce shortest hop-counts, while first-discovery DFS need not? Other shortest-path algorithms can also solve unit-weight graphs; BFS is not the only possible algorithm.

Premise: BFS removes nodes from a FIFO queue, so a node enqueued earlier is always dequeued earlier.

Because: that is the definition of FIFO — the container itself enforces the ordering

Premise: A node at distance d is only ever enqueued by a node at distance d−1, so nodes enter the queue in non-decreasing distance order.

Because: distance increases by exactly 1 per enqueue, and the parent was itself dequeued in order

Premise: Therefore the queue holds, at any moment, only nodes at distance d and d+1 — the frontier is a clean level boundary.

Because: non-decreasing insertion order plus uniform increment cannot produce a gap of 2

Premise: So the first time BFS reaches a node, it reached it via a shortest path — any shorter path would have delivered it in an earlier level, and levels are processed in order.

Because: you cannot arrive early via a long route when all shorter routes were already fully expanded

Premise: DFS has no such property: it commits to one branch to full depth, so it can reach a node by a long path first and only discover a short one much later, after marking it visited.

Because: a stack processes the most recent node, which carries no distance ordering at all

Dijkstra uses a minimum tentative-distance frontier and nonnegative edges. A* adds a heuristic; admissibility, consistency and reopening policy determine which optimality claims hold. Changing the container alone is not a complete proof.

Name: Ripple vs. thread

Picture: BFS is a ripple: drop a stone at the source and the wavefront expands outward, touching everything at distance 1, then everything at distance 2. It knows exactly how far it has gone, and its frontier memory corresponds to the active layers, in addition to its visited/parent state. DFS is a thread through a maze: follow one corridor as far as it goes, then back up to the last junction and try the next one. It has no idea how far it is from the start as the crow flies, and recursive control state follows the active path; visited/output state still grows with reached vertices.

• Frontier policies differ: FIFO supports BFS, recursive/stack frames support DFS, and Dijkstra adds distance relaxation plus nonnegative weights to a minimum-priority frontier. Swapping containers alone does not prove equivalence.

• BFS frontier depends on layer width; recursive DFS control stack depends on depth. Both templates retain O(V) visited/output state. An eager push-all-neighbours stack can also retain a wide frontier, not just the current path.

• Mark on enqueue in this BFS template to guarantee one queue entry per vertex. Other dequeue-marking variants need duplicate-entry guards and may have larger frontiers; they are not automatically incorrect.

• Both are O(V+E) with an adjacency list. For dense graphs E=Θ(V²), that bound is already quadratic even with adjacency lists. Matrix neighbour scans and linear membership tests are other possible causes.

Trigger: Fire this model the moment you see: "fewest steps / degrees of separation" · connected components · cycle detection · topological sort of a pipeline DAG · Airflow task dependency resolution · Spark's lineage graph · dependency install resolution · reachability or blast-radius questions over a lineage graph.

Decision: You must explore a large graph and you can hold only part of it in memory. BFS or DFS?

Name: BFS

Gain: shortest hop-count for free; finds nearby answers fast, so it wins when the target is close to the source; never gets lost down an infinite branch

Cost: a regular search tree can have Θ(b^d) frontier width at depth d for branching b>1; on a stored graph include O(V) discovery/parent state as well

Pick: the answer is expected to be shallow, or you genuinely need the shortest path — social-graph degrees, blast radius within N hops

Name: DFS

Gain: recursive DFS uses O(depth) control frames and naturally supports post-order work, but graph visited/output state is O(V); the eager iterative function below can use O(V) stack space

Cost: no distance guarantee; can wander deep into a useless branch for a long time; a reachable cycle without a guard can prevent termination, while an infinite graph may also defeat a visited-set traversal

Pick: you need to visit everything anyway (so order does not matter), or the graph is wide and shallow answers are not expected — crawlers, dependency resolution, component labelling

Name: Iterative deepening

Gain: depth-limited tree search repeated at increasing limits finds a shallowest goal in a finitely branching, unit-edge search space. A path-local implementation can use O(depth) control state when generating one successor at a time; it does not reproduce BFS’s complete visit order

Cost: re-explores the upper levels on every iteration; the overhead is a constant factor for a regular tree with branching factor greater than one; a chain of goal depth d takes Θ(d²) repeated visits. Graph cycles require path-local checks, and reusing one global visited set across depth limits can incorrectly prune a later valid route

Pick: you need shortest-path semantics but BFS's frontier will not fit — the standard answer in game search and large-state-space exploration

Verdict: Choose the output contract first. BFS gives shortest hop paths; DFS is useful for reachability and ancestor/finish-time structure. Then account for input storage, visited/parent/output state and frontier separately. On a star the eager stack below can hold nearly all vertices; on a chain recursive DFS can exhaust the interpreter budget. Iterative traversal avoids recursive frame limits but not memory limits. Bounded exploration, recomputation or external storage require their own algorithmic contract—switching one container does not make an oversized graph fit.

(c) Hands-on · 25 min

Save as graphs.py. Zero deps beyond stdlib.

"""graphs.py — the interview canon: BFS, DFS, Dijkstra, topological sort.
 
Run:  python graphs.py
"""
from __future__ import annotations
from collections import defaultdict, deque
import heapq
from typing import Optional
 
 
# ------------------------------------------------------------------
# 1) Adjacency-list graph builder — handles both directed + undirected
# ------------------------------------------------------------------
def build_graph(edges: list[tuple[int, int]], directed: bool = False) -> dict[int, list[int]]:
    g: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g
 
 
# ------------------------------------------------------------------
# 2) BFS — shortest edge-count path in an unweighted graph
# ------------------------------------------------------------------
def bfs_shortest(graph: dict[int, list[int]], start: int, goal: int) -> Optional[list[int]]:
    """Return the shortest path (as node list) from start to goal, or None."""
    if start == goal:
        return [start]
    seen = {start}
    parent: dict[int, int] = {}
    q: deque[int] = deque([start])
    while q:
        u = q.popleft()
        for v in graph.get(u, []):
            if v in seen:
                continue
            seen.add(v)
            parent[v] = u
            if v == goal:
                # Reconstruct path
                path = [v]
                while path[-1] != start:
                    path.append(parent[path[-1]])
                path.reverse()
                return path
            q.append(v)
    return None
 
 
# ------------------------------------------------------------------
# 3) DFS — recursive and iterative flavors
# ------------------------------------------------------------------
def dfs_recursive(graph, start, seen=None):
    seen = set() if seen is None else seen
    order = []
    def visit(u):
        seen.add(u)
        order.append(u)
        for v in graph.get(u, []):
            if v not in seen:
                visit(v)
    if start not in seen:
        visit(start)
    return order
 
def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    seen = {start}
    stack = [start]
    order: list[int] = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph.get(u, []):
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return order
 
 
# ------------------------------------------------------------------
# 4) Connected components (undirected graph)
# ------------------------------------------------------------------
def connected_components(graph: dict[int, list[int]], nodes: list[int]) -> list[list[int]]:
    seen: set[int] = set()
    comps: list[list[int]] = []
    for n in nodes:
        if n in seen:
            continue
        comp = dfs_iterative(graph, n)
        seen.update(comp)
        comps.append(comp)
    return comps
 
 
# ------------------------------------------------------------------
# 5) Dijkstra — shortest path with non-negative weights (S029 reuse)
# ------------------------------------------------------------------
def dijkstra(graph: dict[int, list[tuple[int, float]]], start: int) -> dict[int, float]:
    """Finite graph, integer labels, finite nonnegative weights; reachable only.
 
    Integer inputs accumulate exactly; float inputs use floating arithmetic.
    No validation: negative edges/cycles are outside the Dijkstra contract.
    """
    dist: dict[int, float] = {start: 0}
    heap: list[tuple[float, int]] = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                                            # stale entry
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist
 
 
# ------------------------------------------------------------------
# 6) Topological sort (Kahn's algorithm) — dependency order
# ------------------------------------------------------------------
def topological_sort(graph: dict[int, list[int]], nodes: list[int]) -> Optional[list[int]]:
    """Return a valid topological order for the DAG, or None if there's a cycle."""
    indeg: dict[int, int] = {n: 0 for n in nodes}
    for u in nodes:
        for v in graph.get(u, []):
            indeg[v] = indeg.get(v, 0) + 1
    q: deque[int] = deque([n for n in nodes if indeg[n] == 0])
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == len(nodes) else None          # None → cycle detected
 
 
# ------------------------------------------------------------------
# 7) Cycle detection in a directed graph (three-colour DFS)
# ------------------------------------------------------------------
def has_cycle_directed(graph: dict[int, list[int]], nodes: list[int]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in nodes}
 
    def visit(u: int) -> bool:
        color[u] = GRAY
        for v in graph.get(u, []):
            if color.get(v, WHITE) == GRAY:                     # back-edge → cycle
                return True
            if color.get(v, WHITE) == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False
 
    return any(color[n] == WHITE and visit(n) for n in nodes)
 
 
# ------------------------------------------------------------------
# Runner
# ------------------------------------------------------------------
if __name__ == "__main__":
    # Undirected graph:
    #  1 - 2 - 3
    #  |       |
    #  4 - 5 - 6
    edges = [(1, 2), (2, 3), (1, 4), (4, 5), (5, 6), (3, 6)]
    g = build_graph(edges)
    print("BFS 1 -> 6:", bfs_shortest(g, 1, 6))
    print("DFS from 1 (recursive):", dfs_recursive(g, 1))
    print("DFS from 1 (iterative):", dfs_iterative(g, 1))
    print("connected_components:", connected_components(g, [1, 2, 3, 4, 5, 6, 7, 8]))   # 7 & 8 isolated
 
    # Weighted directed graph for Dijkstra
    weighted = {
        1: [(2, 7.0), (3, 9.0), (6, 14.0)],
        2: [(3, 10.0), (4, 15.0)],
        3: [(4, 11.0), (6, 2.0)],
        4: [(5, 6.0)],
        5: [],
        6: [(5, 9.0)],
    }
    print("Dijkstra from 1:", dijkstra(weighted, 1))
 
    # DAG for topological sort — a tiny ‘build system’
    dag = build_graph([("compile", "link"), ("test", "package"), ("link", "package"), ("bootstrap", "compile"), ("bootstrap", "test")], directed=True)
    all_nodes = ["bootstrap", "compile", "link", "test", "package"]
    print("topological_sort:", topological_sort(dag, all_nodes))
    print("has_cycle (DAG):", has_cycle_directed(dag, all_nodes))
 
    # Add a cycle: package -> bootstrap
    dag2 = build_graph([("compile", "link"), ("test", "package"), ("link", "package"), ("bootstrap", "compile"), ("bootstrap", "test"), ("package", "bootstrap")], directed=True)
    print("has_cycle (with cycle):", has_cycle_directed(dag2, all_nodes))
    print("topological_sort (cyclic):", topological_sort(dag2, all_nodes))

Anatomy of the script

What each function teaches

Name: build_graph

Desc: The default representation — dict[node → list[neighbor]]. Directed or undirected via a single flag.

Name: bfs_shortest

Desc: The canonical unweighted-shortest-path template. seen set prevents cycles; parent dict lets you reconstruct the path.

Name: dfs_recursive vs dfs_iterative

Desc: Both return reachable vertices but need not form the same DFS tree. Recursion has a configurable depth limit; iteration avoids recursive frames but remains memory-bounded. Eager marking of all pushed neighbours cannot be used as recursive DFS finish/ancestor order.

Name: connected_components

Desc: Loop over all nodes; if unvisited, DFS from it → that DFS returns one whole component. Union-find would also work.

Name: dijkstra

Desc: The S029 lazy-heap pattern for nonnegative additive costs, not a universal template for all weighted graphs.

Name: topological_sort

Desc: Kahn's algorithm — process nodes with no unmet dependencies first, decrement successors. If output size < V, there was a cycle.

Name: has_cycle_directed

Desc: Three-colour DFS: WHITE = unvisited, GRAY = currently on the stack, BLACK = fully processed. A back-edge to a GRAY node = cycle.

What to observe when you run it

BFS 1→6 returns [1, 2, 3, 6] for this edge insertion order: four vertices, three edges. Reordering neighbours can choose the equally short [1, 4, 5, 6]. DFS from 1 visits every reachable node. Stack LIFO changes visit order, and eager discovery can change the tree itself; merely reversing the neighbour list does not always recover recursive DFS order. connected_components returns 3 groups: {1..6}, {7}, {8}. Dijkstra dist[5] = 20 (path 1 → 3 → 6 → 5 = 9 + 2 + 9 = 20). topological_sort on the DAG returns a valid order (‘bootstrap’ first, ‘package’ last). has_cycle: False for the DAG, True once we add package → bootstrap; topological_sort then returns None.

Goal: Implement ‘number of islands’ (classic grid BFS/DFS)

Hint: Treat the 2D grid as an implicit graph — each ‘1’ cell has up to 4 neighbors (up/down/left/right). Loop over all cells; when you find an unvisited ‘1’, DFS/BFS to mark the whole island and increment the count.

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen: set[tuple[int, int]] = set()
 
    def dfs(r: int, c: int) -> None:
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            if (r, c) in seen or r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
                continue
            seen.add((r, c))
            stack.extend([(r+1, c), (r-1, c), (r, c+1), (r, c-1)])
 
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                dfs(r, c)
                count += 1
    return count
 
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
print(num_islands(grid))   # 3

Exercise answer: the 4-neighbour grid has three components: the upper-left 2×2 block, the centre cell, and the bottom-right pair. Diagonally touching cells are not connected. num_islands accepts a rectangular list of rows; [] and rows of zero width return 0. Only the string "1" is land; the input is not mutated. Ragged rows are outside the contract. Each land cell is expanded once and adds at most four stack candidates, so time and auxiliary space are O(rows×cols), even though a candidate may be pushed more than once.

Vertex, ordering and complexity contracts

build_graph retains edge insertion order, parallel edges and self-loops. Directed destination-only vertices may lack dictionary keys; get(u, []) treats them as sinks. Isolated vertices are not recoverable from an edge list alone, so keep a separate vertex list. bfs_shortest accepts arbitrary hashable labels despite the int annotation: -1 is not reserved. If start==goal it returns [start] even for an isolated/undeclared vertex; otherwise it returns an actual path or None. Ties follow neighbour iteration order, not lexicographic sorting. All graph functions leave adjacency lists unchanged; dfs_recursive intentionally adds to a supplied seen set and returns [] if start was already seen.

For component enumeration require an undirected symmetric adjacency relation and a complete vertex list including isolated vertices. A directed graph needs a separate weak/strong component definition. For topological sort and directed-cycle detection require a unique, complete vertex list containing all adjacency keys and endpoints; inputs are not validated. Under that contract every parallel edge increments/decrements in-degree once, a self-loop is a cycle, and isolated vertices appear in the output. An incomplete list must not be mistaken for proof of a cycle or a complete ordering.

BFS/DFS cost O(V+E) over the reached adjacency-list subgraph (expected constant-time hash operations); full components/Kahn/three-colour scans cost O(V+E). They retain O(V) discovery/output state in addition to O(V+E) graph storage. Recursive depth is at most V; dfs_iterative can retain O(V) eager frontier entries. Kahn's queue contains exactly currently eligible unprocessed vertices, and its residual in-degree counts incoming edges from unprocessed vertices. Three-colour DFS tests GRAY ancestors, not merely already-seen vertices: a shared BLACK descendant in a diamond DAG is not a cycle.

The lazy Dijkstra loop uses O((V+E) log(E+2)) time and O(V+E) auxiliary state in the reachable graph. Its nonnegative-weight proof finalises a nonstale minimum; obsolete entries must not expand their outgoing edges again. Integer weights now stay exact instead of being rounded by a 0.0 initial heap distance. Float sums can round or overflow, so applications needing exact decimal costs must choose an appropriate numeric model. Negative edges invalidate the proof, not necessarily every finite output of this re-relaxing implementation; a reachable negative cycle can make it run indefinitely.

(d) Production reality · 15 min

Resolve versions before ordering installation

A dependency edge can mean “requires some version satisfying these constraints.” Choosing compatible versions is a constraint problem; pip documents backtracking when an earlier choice conflicts with later requirements. A topological order applies only after a suitable acyclic task graph is chosen. A→B and B→A defeats a DAG install-order model, but that alone is not proof that every package manager rejects all circular package dependencies. Do not attribute an hour-long npm incident or one SAT implementation to this toy Kahn loop.

Social associations are data, not a universal recommendation algorithm

Meta's TAO describes objects and typed associations with graph-oriented access on persistent MySQL storage and caches. Two-hop traversal can generate candidates, but ranking, visibility/privacy checks, fan-out limits and cache policy remain separate. For a high-degree vertex, bound fetched neighbours or page the work rather than assuming every friend-of-friend query is a sub-10-ms BFS. A relational join can be a valid implementation; graph structure does not prove SQL is unsuitable.

Route preprocessing does not change the cost contract

Dijkstra is a baseline for finite nonnegative weighted graphs. Precomputed shortcuts and bidirectional search can accelerate suitable repeated route queries, but this lesson neither implements those accelerations nor verifies a proprietary service or claimed seconds-to-milliseconds result. OSPF is a concrete source-backed shortest-path-tree application. Keep routing policy (for example BGP path attributes) distinct from shortest additive distance.

Where this shows up in the rest of the plan

Root: Graphs are the universal shape

Label: S033 · Dynamic Programming

Desc: A DAG permits dependency-ordered dynamic programming, including longest-path relaxation. Longest path on general cyclic graphs is a different problem.

Label: Further connection · Build systems and CI

Desc: A task DAG exposes a partial order; execution also needs caching, resource limits and failure handling beyond topological sorting.

Label: Further connection · Concurrency and deadlocks

Desc: For a single-instance resource wait-for model, a directed cycle signals deadlock. Multiple instances and other waiting semantics need a richer test.

Label: Further connection · Knowledge-graph retrieval

Desc: Graph retrieval may expand edges, then filter/rank evidence; it is not necessarily a plain traversal or a shortest-path task.

Label: Further connection · Distributed consensus

Desc: Protocol participants communicate over a network graph; Raft/Paxos agreement requires protocol rules, not just gossip or traversal.

Label: Further connection · Query optimisation

Desc: Query plans can be trees/DAGs; optimisers choose operators, access paths and join orders using cost models, not merely a topological permutation.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — questions and worked answers

Q: What are the three main graph representations, and which is the default in real code?

A: Adjacency list (dict of neighbor lists), adjacency matrix (V×V), edge list. Adjacency list is the default — sparse-friendly and fast to iterate neighbors.

Q: What does BFS give you that DFS does not?

A: Shortest path (in edge count) from the start to every reachable node in an unweighted graph. DFS goes deep and does NOT guarantee shortest.

Q: Why do these general reachability traversals track visited vertices, and when can that be replaced?

A: Discovery tracking avoids repeated expansion in cycles and shared paths. A child-only tree needs none under its tree contract; an undirected tree needs at least a parent check. Other algorithms may use colours, distance labels or path-local checks instead of one global set.

Q: Explain Dijkstra's algorithm in two sentences.

A: Use a min-heap of (tentative_dist, node); pop the closest unfinalised node, relax outgoing edges (update dist if shorter, push new heap entry). Ignore stale heap entries via the ‘if d > dist[u], skip’ check.

Q: What is a topological sort, and what problems does it solve?

A: An ordering of DAG nodes with u before v for every edge (u,v). It orders selected acyclic dependencies such as build tasks, prerequisite courses or spreadsheet formulas; package version solving and resource scheduling are additional problems.

Q: Give the outline of Kahn's algorithm for topological sort.

A: Given a complete unique vertex list, compute in-degrees and queue all zero-in-degree nodes. Pop, output, decrement successor in-degrees and enqueue newly zero ones. If output length is less than V, the declared directed graph contains a cycle.

Q: How does three-colour DFS detect a cycle in a directed graph?

A: WHITE = unvisited, GRAY = currently on the DFS stack, BLACK = fully processed. If during DFS you encounter a GRAY neighbor, that's a back-edge → cycle.

Q: Why doesn't Dijkstra work with negative edge weights?

A: The first nonstale minimum is final only under the nonnegative-weight proof. A later negative edge can improve a settled node. This lab’s re-relaxing loop may repair some negative-edge cases, but its Dijkstra bound no longer holds and a reachable negative cycle can prevent termination. Use an algorithm with an explicit negative-edge/cycle contract, such as Bellman–Ford or DAG relaxation.

Q: What's the time complexity of BFS/DFS on an adjacency list?

A: O(V+E) for the reached adjacency-list subgraph under constant expected hash costs. Each reached vertex is expanded once; each stored adjacency entry is scanned once (an undirected edge normally has two entries). Output/discovery memory is O(V).

Q: Stretch — design a way to detect if a graph is bipartite in O(V + E).

Stretch: true

A: BFS from any node; colour it 0, colour its neighbors 1, their neighbors 0, and so on. If BFS ever tries to colour a neighbor the same colour as the current node, the graph is NOT bipartite. Repeat for each connected component. For undirected graphs, bipartiteness = 2-colourability = no odd-length cycles, including self-loops as length-one cycles.

Bipartiteness: executable stretch answer

def is_bipartite(graph, nodes):
    """Complete vertex list and symmetric undirected adjacency; no mutation."""
    color = {}
    for start in nodes:
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph.get(u, []):
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True
 
assert is_bipartite({0: [1], 1: [0], 2: []}, [0, 1, 2])
assert not is_bipartite({0: [1, 2], 1: [0, 2], 2: [0, 1]}, [0, 1, 2])

Each disconnected component needs a fresh seed. A self-loop rejects immediately; duplicate edges do not change the answer. Time O(V+E), auxiliary space O(V).

Explain-out-loud test

Teach these three, one minute each, no notes:

1. What is a graph, and give one real-world example.
2. When do you use BFS vs DFS?
3. What does topological sort do, and give one system that uses it.

Grind this pattern in the LeetCode track

This session builds the mental model for graphs. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L27 · Graphs I (DFS) · L28 · Graphs II (BFS) · L29 · Graphs III (Topo) · L30 · Graphs IV (Union-Find)

Do the concept here, then go there to build the reflex.

Explain-out-loud answer guide

1. A graph specifies vertices plus edges with direction/cost semantics. A prerequisite task graph models “must finish before”, unlike an undirected friendship graph.
2. Use BFS for fewest-hop paths and layer order, DFS for reachability or properly tracked ancestor/finish structure, and Dijkstra for nonnegative additive costs. Include discovery/output memory in every comparison.
3. A topological order puts every dependency before its consumer. Kahn queues zero residual in-degree vertices; a complete unique vertex universe is required before leftover nodes certify a cycle.

What comes next

Next: S031 · Sorting — Merge, Quick, and When to Trust the Built-in

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

Primary passages checked 2026-10-10; saved raw/canonical evidence and bounded exact-program tests support the named contracts, not production benchmarks or whole-site approval.

• Princeton Algorithms: directed graphs
• Princeton Algorithms: shortest paths
• pip dependency resolution
• Meta: TAO and graph data
• OSPF specification RFC 2328 §16.1