BFS and DFS in Production

Web Crawler: BFS on the Web Graph

A web crawler’s job is to discover and index the web. The web is a directed graph: pages are nodes; hyperlinks are directed edges. The crawler starts at seed URLs and expands outward, discovering new pages by following links.

BFS is the correct traversal because BFS explores pages closest to the seeds first. This matters for relevance: pages linked from authoritative starting points are more important than pages reachable only through long chains. A BFS crawler stays close to the seed set for longer; a DFS crawler might dive into one remote corner of the web and not return to the main body for a long time.

from collections import deque
from urllib.parse import urlparse
import time

class WebCrawler:
    """
    BFS web crawler with politeness delays and domain rate limiting.
    """
    def __init__(self, seed_urls: list[str], max_pages: int = 1000):
        self.frontier: deque[str] = deque(seed_urls)
        self.visited: set[str] = set(seed_urls)
        self.max_pages = max_pages
        self._last_visit: dict[str, float] = {}  # domain -> last fetch time

    def _is_polite(self, url: str, delay_seconds: float = 1.0) -> bool:
        """
        Politeness: do not fetch from the same domain more than once per delay_seconds.
        This prevents overloading individual servers.
        """
        domain = urlparse(url).netloc
        now = time.time()
        last = self._last_visit.get(domain, 0)
        return now - last >= delay_seconds

    def _fetch_and_extract_links(self, url: str) -> list[str]:
        """Fetch page and extract links. Real implementation uses HTTP client + HTML parser."""
        self._last_visit[urlparse(url).netloc] = time.time()
        # In production: HTTP GET, parse HTML, extract <a href="...">
        return []  # placeholder

    def crawl(self) -> list[str]:
        """BFS crawl. Returns list of visited URLs in BFS order."""
        visited_order = []

        while self.frontier and len(visited_order) < self.max_pages:
            url = self.frontier.popleft()  # FIFO: process oldest-discovered URLs first

            if not self._is_polite(url):
                self.frontier.append(url)  # requeue for later
                continue

            links = self._fetch_and_extract_links(url)
            visited_order.append(url)

            for link in links:
                if link not in self.visited:
                    self.visited.add(link)
                    self.frontier.append(link)  # add to back of queue (BFS)

        return visited_order

The visited set is the critical component. Without it, BFS on a graph with cycles is infinite — the crawler would follow A→B→A→B forever. The visited set ensures each node is processed once: O(V + E) total work.

The frontier can grow very large. A BFS that fans out aggressively can have millions of URLs in the frontier at once. Memory management of the frontier is a practical constraint that textbook BFS ignores: production crawlers use a combination of in-memory queues and on-disk queues (priority queues sorted by page rank estimate or domain).

Dependency Resolution: DFS on the Dependency DAG

A package manager must install all transitive dependencies of a requested package and determine the correct installation order (each dependency before the packages that depend on it). This is DFS on a dependency graph, combined with topological sort (Chapter 8).

DFS is appropriate here because we need complete dependency trees — we want to follow one path to its leaf (a package with no further dependencies) before backtracking. BFS would give us all level-1 dependencies before level-2 dependencies; DFS gives us a complete path, which is what recursive installation needs.

def resolve_dependencies(
    package: str,
    registry: dict[str, list[str]]
) -> list[str]:
    """
    DFS dependency resolution.
    registry: package_name -> [direct_dependencies]
    Returns installation order: dependencies before the packages that need them.
    Raises ValueError on circular dependency.
    """
    resolved: list[str] = []
    visiting: set[str] = set()   # currently in the DFS call stack (cycle detection)
    visited: set[str] = set()    # fully resolved

    def dfs(pkg: str) -> None:
        if pkg in visited:
            return
        if pkg in visiting:
            raise ValueError(f"Circular dependency detected: {pkg}")

        visiting.add(pkg)

        for dep in registry.get(pkg, []):
            dfs(dep)  # Resolve dependency first (DFS goes deep before backtracking)

        visiting.discard(pkg)
        visited.add(pkg)
        resolved.append(pkg)  # Add after all dependencies are resolved (post-order)

    dfs(package)
    return resolved

# Example: flask -> werkzeug, click; click -> colorama
registry = {
    'flask': ['werkzeug', 'click'],
    'click': ['colorama'],
    'werkzeug': [],
    'colorama': []
}

order = resolve_dependencies('flask', registry)
# order: ['werkzeug', 'colorama', 'click', 'flask']
# Dependencies always appear before the packages that need them

The two-set cycle detection (visiting vs visited) is essential. visiting tracks the current DFS path: if we encounter a node already in visiting, we have found a back edge — a cycle. visited tracks fully processed nodes: we do not re-process them.

Garbage Collection: BFS/DFS from GC Roots

A garbage collector identifies unreachable objects and reclaims their memory. The memory graph: every object is a node; every object reference (a pointer from one object to another) is a directed edge.

The mark phase of a mark-and-sweep GC is BFS or DFS starting from the GC roots — a set of guaranteed-live objects: global variables, stack-allocated variables, registers. Any object reachable from a root is live; anything not reachable is garbage.

class Object:
    def __init__(self, name: str):
        self.name = name
        self.references: list['Object'] = []  # outgoing references
        self.marked = False

def mark_phase(roots: list[Object]) -> set[Object]:
    """
    BFS mark phase: traverses the object reference graph from GC roots.
    Marks all reachable objects as live.
    Returns the set of live objects.
    """
    live = set()
    frontier = deque(roots)

    while frontier:
        obj = frontier.popleft()
        if obj in live:
            continue
        live.add(obj)
        obj.marked = True

        for referenced in obj.references:
            if referenced not in live:
                frontier.append(referenced)

    return live

def sweep_phase(all_objects: list[Object], live: set[Object]) -> list[Object]:
    """
    Sweep phase: free all objects not marked as live.
    Returns the list of collected (freed) objects.
    """
    garbage = [obj for obj in all_objects if obj not in live]
    # In a real GC, freed memory is returned to the allocator
    return garbage

The GC traversal must be conservative: it marks everything reachable, even if some reachable objects will never be accessed again by the program. This is the fundamental limitation of tracing GC — it cannot distinguish “reachable but will never be used” (a memory leak) from “reachable and needed.” This is why long-lived data structures that accumulate references cause memory leaks even in garbage-collected languages.

DFS as Combinatorial Search: The Backtracking Discipline

A PostgreSQL query joins five tables. The planner must choose the order in which to join them — with 5 tables, there are 120 possible orderings, and the wrong choice can be a thousand times slower than the right one. The planner does not evaluate all 120. It walks a tree of partial join plans, extending the current plan one table at a time, and abandons a partial plan the moment its estimated cost exceeds the best complete plan found so far. Extend, evaluate, retract.

A Kubernetes admission controller checks that a new pod’s resource requests fit an existing node’s remaining capacity while respecting affinity rules, taints, and priority classes. It tries each candidate node in turn; on rejection, it undoes any speculative bindings and tries the next. Extend, check, retract.

A Sudoku solver picks an empty cell, tries 1, recurses; on failure it erases the 1, tries 2, recurses. Extend, check, retract.

This is not a new algorithm. It is DFS on an implicit graph — the graph of partial configurations — with two invariants added: the current path is mutated in place as we descend, and restored to its previous state as we return. The recurse-mutate-unmutate idiom is the whole difference between backtracking and the DFS you already wrote.

def solve_nqueens(n: int) -> list[list[int]]:
    """
    Place n queens on an n×n board with no two on the same row, column, or diagonal.
    Returns list of solutions; each solution is a list where board[row] = column.
    Complexity: O(n!) worst case; column/diagonal pruning cuts this dramatically.
    """
    solutions: list[list[int]] = []
    board: list[int] = []           # board[row] = column of the queen in that row
    cols: set[int] = set()          # occupied columns
    diag1: set[int] = set()         # occupied "/" diagonals (row - col)
    diag2: set[int] = set()         # occupied "\" diagonals (row + col)

    def backtrack(row: int) -> None:
        if row == n:
            solutions.append(board.copy())   # complete configuration: record
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue                     # pruned: this partial placement is dead

            # Extend: mutate state to reflect placing a queen at (row, col)
            board.append(col)
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)               # recurse into the extended state

            # Retract: restore state exactly as it was before we placed the queen
            board.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

The three set structures do the pruning: a partial placement that violates a constraint is abandoned immediately, without recursing further. This is what turns O(n!) worst-case into something tractable for n=8 — ~2,000 recursive calls to find all 92 solutions, not 40,320.

Backtracking’s real cost is not the recursion — it is the state restoration. Every mutation on the way down needs a matching un-mutation on the way back up. A single missed restore corrupts the search: subsequent branches inherit stale state and either miss valid solutions or accept invalid configurations silently (FM9). The tightest backtracking implementations avoid this by never mutating shared state — passing an immutable partial configuration into each recursive call — but the allocation cost of that discipline is often prohibitive on large search spaces.

The three systems that opened this section — query planner, admission controller, Sudoku solver — differ only in what the “constraint check” and the “extend” step do. The traversal shape is identical.

Level 1 — Understand

1. What data structure does BFS use? What data structure does DFS use? How does the choice of data structure determine the traversal order?

2. What is a GC root? Why does a garbage collector start its traversal from roots rather than from all objects?

3. A dependency graph has a cycle: A depends on B and B depends on A. What happens when DFS traverses this graph without cycle detection? How does the two-set approach detect the cycle?

Level 2 — Apply

A social network has 1 million users. Each user has on average 200 connections. You need to find all users reachable from user X within 3 “degrees of separation” (3 hops).

1. Which traversal would you use? Justify with reference to the properties of BFS vs DFS.

2. What is the maximum number of nodes in the BFS frontier at depth 3?

3. The frontier at depth 3 exceeds available memory. Propose a modification to the traversal that bounds memory usage while still returning results.

Level 3 — Design

You are building a dependency analysis service for a large monorepo with 50,000 modules. Engineers want to know: (a) what is the full transitive dependency set of module X, and (b) which modules transitively depend on module Y (reverse dependency lookup).

1. Choose a traversal for each query. Design the data structures for forward and reverse dependency graphs.

2. The dependency graph changes ~500 times per day as engineers modify module dependencies. How do you keep the forward and reverse graphs consistent on change?

3. Query (a) is called 10,000 times per day; the same modules are queried repeatedly. Design a caching strategy for dependency sets. Name every tradeoff using AT notation.

A complete answer will: separate the claim from its justification, name the tradeoff and failure mode by code, and state the assumption that the argument depends on.