S030 · Graphs — Representation, BFS, DFS, Shortest Path

Module M03: Data Structures & Algorithms · Session 30 of 130 · Track: SW 🕸️

What you'll be able to do after this session

• Explain Graphs to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S028 — Trees & BSTs — Traversal (BFS/DFS)

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Graphs explained (NeetCode) — the vocabulary in 10 minutes.
• 🎥 Deep dive (30–60 min) · MIT 6.006 — BFS and DFS (Erik Demaine) — the algorithms, formally.
• 🎥 Hands-on demo (10–20 min) · BFS and DFS coded live in Python (NeetCode) — traversal patterns you'll reuse for months.
• 📖 Canonical article · Wikipedia — Breadth-first search — the algorithm, cleanly stated.
• 📖 Book chapter / tutorial · cp-algorithms — BFS and DFS — competitive-programming style walkthroughs with variants.
• 📖 Engineering blog · Neo4j — What is a graph database? — how graphs become production storage engines.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Networks, relationships, roads — all graphs.

A graph is the most general "things and connections between them" structure computers know how to work with. Trees were graphs with two rules (one root, no cycles); once you drop those rules you get a graph. Formally: a set of nodes (a.k.a. vertices) and a set of edges (each edge connects two nodes, optionally with a direction and/or a weight).

Graphs model everything: social networks (people → friendships), the web (pages → links), road maps (intersections → roads), Kubernetes deployments (containers → dependencies), git commits, file systems with hard links, code call graphs, recommendation systems. The whole reason modern data infrastructure has a "graph database" category (Neo4j, TigerGraph, Amazon Neptune) is that many real questions ("shortest path", "friends of friends", "impact of removing this service") are much cleaner in a graph model than in a table model.

Two canonical ways to walk a graph:

• BFS (Breadth-First Search) — explore level by level using a queue. Finds shortest paths in unweighted graphs. Used for "how many hops away is X?", crawlers, and level-order tree traversal.
• DFS (Depth-First Search) — dive deep first using a stack (or recursion). Used for cycle detection, topological sort, connected components, and any "does a path exist?" question.

One-sentence gotcha to carry forever: Forgetting to mark nodes as visited turns any graph traversal into an infinite loop — a cycle sends you round and round. Every BFS/DFS starts with an empty visited set, and every neighbour check gates on if neighbour not in visited. Miss this line and you'll hang.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

A tiny undirected graph:

Two ways to represent it in code:

1. Adjacency list (dict of node → list of neighbours) — sparse, most common:

{"A": ["B","C"], "B": ["A","D"], "C": ["A","D","F"],
 "D": ["B","C","E"], "E": ["D"], "F": ["C"]}

Space: O(V + E). Best for sparse graphs (most real-world graphs are sparse).

2. Adjacency matrix (V×V grid, 1 if edge exists) — dense:

    A B C D E F
A [ 0 1 1 0 0 0 ]
B [ 1 0 0 1 0 0 ]
...

Space: O(V²). Good for dense graphs, fast edge-existence lookup.

Worked example — BFS from A, looking for shortest path to E:

Queue starts with [(A, dist=0)], visited = {A}.

Shortest path A→E = 3 hops. BFS guarantees this because it explores nodes in order of distance from the start.

DFS from A (recursive, using a stack implicitly):

Visit order (one possibility, depends on neighbour ordering): A → B → D → C → F → E. Notice DFS goes deep before wide — it might traverse a 100-hop path before checking the immediate neighbour of A.

When to reach for which:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# graphs_playground.py
from collections import deque, defaultdict
 
# ---- 1. Build an adjacency list ----
edges = [("A","B"),("A","C"),("B","D"),("C","D"),("D","E"),("C","F")]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # undirected
 
print("neighbours of A:", graph["A"])
print("neighbours of D:", graph["D"])
 
# ---- 2. BFS: shortest path length from src to every reachable node ----
def bfs_distances(graph, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist
 
print("
BFS distances from A:", dict(bfs_distances(graph, "A")))
 
# ---- 3. BFS with path reconstruction ----
def shortest_path(graph, src, dst):
    if src == dst: return [src]
    parent = {src: None}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in parent:
                parent[v] = u
                if v == dst:
                    path = []
                    cur = v
                    while cur is not None:
                        path.append(cur)
                        cur = parent[cur]
                    return path[::-1]
                q.append(v)
    return None
 
print("shortest A->E:", shortest_path(graph, "A", "E"))
 
# ---- 4. DFS: recursive ----
def dfs_recursive(graph, u, visited=None, order=None):
    if visited is None: visited, order = set(), []
    visited.add(u); order.append(u)
    for v in graph[u]:
        if v not in visited:
            dfs_recursive(graph, v, visited, order)
    return order
 
print("
DFS recursive from A:", dfs_recursive(graph, "A"))
 
# ---- 5. DFS: iterative with explicit stack ----
def dfs_iterative(graph, src):
    visited, order, stack = set(), [], [src]
    while stack:
        u = stack.pop()
        if u in visited: continue
        visited.add(u); order.append(u)
        for v in reversed(graph[u]):   # reversed to mimic recursive order
            if v not in visited: stack.append(v)
    return order
 
print("DFS iterative from A:", dfs_iterative(graph, "A"))
 
# ---- 6. Cycle detection in a directed graph (DFS with 3 colours) ----
def has_cycle_directed(graph, nodes):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in nodes}
    def visit(u):
        color[u] = GRAY
        for v in graph.get(u, []):
            if color.get(v, WHITE) == GRAY: return True
            if color.get(v, WHITE) == WHITE and visit(v): return True
        color[u] = BLACK
        return False
    return any(visit(n) for n in nodes if color[n] == WHITE)
 
dag = {"A":["B"], "B":["C"], "C":[]}
cyc = {"A":["B"], "B":["C"], "C":["A"]}
print("
cycle in DAG   :", has_cycle_directed(dag, ["A","B","C"]))
print("cycle in cyclic:", has_cycle_directed(cyc, ["A","B","C"]))

Checklist:

1. graph["A"] = ['B', 'C'].
2. BFS distances: {A:0, B:1, C:1, D:2, F:2, E:3}.
3. shortest_path("A","E") returns something like ['A','B','D','E'] or ['A','C','D','E'] (both length 4 nodes = 3 hops).
4. DFS recursive and iterative visit all 6 nodes.
5. Cycle detection: False on DAG, True on cyclic graph.

Try this modification: implement connected_components(graph) that returns a list of sets, one per connected component. Test it on a graph with two disconnected pieces. Then upgrade to counting the size of the largest component — a classic interview question.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Graphs are the mental model behind more production systems than you'd guess:

1. Social networks and recommendation. Facebook, LinkedIn, Twitter, Instagram — every "people you may know" or "recommended for you" surface is either literally a graph query (friends-of-friends BFS at bounded depth) or a graph-embedding lookup (nodes projected to vectors, then nearest-neighbour). LinkedIn's original Economic Graph and Facebook's TAO ("The Associations and Objects") both surfaced graph traversal as a first-class API.

2. Routing and mapping. Google Maps, Uber ETA, delivery routing (DoorDash, Amazon Logistics) all model roads as weighted graphs and use variants of Dijkstra / A* / contraction hierarchies. At the internet layer, BGP (Border Gateway Protocol) is literally routers exchanging graph info about who they can reach.

3. Infrastructure dependency graphs. Kubernetes deployment order, Terraform apply plans, Bazel/Make build systems, npm dependency resolution, Airflow DAGs — all are topological sorts over directed acyclic graphs. Whenever you hear "cycle detected" as an error, DFS ran and found a back-edge.

4. Search and knowledge graphs. Google's Knowledge Graph, Amazon's product graph, and the entire LLM-era "retrieval over knowledge graphs" wave. The graph is often the structured backbone; ML models fill in fuzzy edges (embeddings, similarity).

5. Fraud detection. "Ring detection" in payments — one bad card links to N accounts links to N devices links to M more cards. Traversing that graph to a bounded depth surfaces coordinated fraud rings that per-account rules miss entirely. Uber, PayPal, and Stripe all publish on this.

Common bugs and gotchas:

• Blowing memory on the visited set in massive graphs. Facebook-scale traversals use approximate structures (Bloom filters, HyperLogLog) instead of exact sets.
• Recursive DFS crashing on deep graphs. Linear chains of a million nodes exceed default recursion limits. Always have an iterative version ready.
• Confusing "shortest path" definitions. In weighted graphs, BFS gives wrong answers — you need Dijkstra. In graphs with negative weights, Dijkstra gives wrong answers — you need Bellman-Ford. Match the algorithm to the edge semantics.
• Directed vs undirected slip-ups. Adding one edge to an adjacency list creates a one-way edge unless you explicitly add the reverse. Countless bugs.
• Assuming BFS/DFS gives the order. The order depends on how neighbours are listed. Two runs of the same code on the same graph can produce different outputs — deterministic only if you sort neighbours.

Graph databases as a category. Neo4j, Neptune, JanusGraph, TigerGraph, Dgraph — the promise is "queries that would be 5 joins in SQL become a 1-line Cypher/Gremlin traversal." Reality is more nuanced: for point lookups relational still wins; for multi-hop or shape-matching queries the graph engine dominates. LinkedIn's Databus / DataHub and Uber's dependency graph both illustrate real-world adoption patterns.

(e) Quiz + exercise · 10 min

1. What is the difference between a tree and a graph?
2. Given an unweighted graph, which of BFS or DFS finds the shortest path — and why?
3. Explain the "visited set" and what happens if you forget it.
4. Contrast adjacency list vs adjacency matrix in terms of space and edge-lookup time.
5. When should you use DFS specifically (over BFS)? Give at least two concrete tasks.

Stretch (connects to S029 — Heaps): Modify the BFS shortest_path code to work on a weighted graph. Which data structure does the queue become, and why does BFS with a plain queue fail on weighted graphs?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Graphs? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S031): Sorting — Merge, Quick, and When to Trust the Built-in
• Previous (S029): Heaps & Priority Queues
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.