Graphs

A graph is a set of things (vertices) and the connections between them (edges) — a friend network on a social app, a road map, a dependency chain between build targets, the "who calls whom" structure of a service architecture. It is the most general structure in this whole series: a linked list is a graph where every node has at most one outgoing edge, a tree is a graph with no cycles and exactly one path between any two nodes. Interviewers reach for graphs because so many real systems are graphs in disguise — "can user A reach user B," "is there a cycle in this build dependency," "what order do these tasks need to run in" — and because graph problems reward the same short list of traversal techniques applied carefully, rather than memorized tricks.

Deep Dive: Vertices, Edges, and the Vocabulary That Actually Matters

A vertex is a single entity; an edge is a connection between two vertices. Undirected means the edge works both ways — if A is friends with B, B is friends with A, so the edge A-B is one fact, not two. Directed means the edge has a specific direction — a road that's one-way, a Twitter "follows" relationship, a prerequisite ("course A must come before course B"), where A->B does not imply B->A. Weighted means each edge carries a number (distance, cost, latency); unweighted treats every edge as costing the same "one step." These four words — directed/undirected, weighted/unweighted — are the first thing to pin down about any graph problem, because they change which algorithms are even valid: BFS finding shortest paths, for instance, only holds for unweighted graphs, covered in detail below.

A vertex's degree is its number of edges (in an undirected graph); a directed graph splits this into in-degree (edges pointing in) and out-degree (edges pointing out) — in-degree is exactly what topological sort's Kahn's algorithm uses, covered later on this page. A path is a sequence of vertices connected by edges; a cycle is a path that returns to its starting vertex. A graph with no cycles is acyclic; a directed acyclic graph (DAG) is the structure behind build systems, spreadsheet formula dependencies, and task schedulers.

Deep Dive: Adjacency Matrix vs Adjacency List

An adjacency matrix is a V×V grid where cell [i][j] says whether an edge exists from vertex i to vertex j (and its weight, if weighted, instead of just 1). It costs O(V²) space no matter how sparse the graph is, because it reserves a cell for every possible pair of vertices, edge or not. In exchange, "does an edge exist between these two specific vertices" is a single array lookup, O(1). An adjacency list stores, per vertex, only the neighbors that actually exist — its space is O(V+E): V for the list of vertices, E for the total edge entries across all of them (E doubled for an undirected graph, since each edge appears in both endpoints' lists). Checking "does this exact edge exist" now costs O(degree of that vertex) since you have to scan a list, but listing all of a vertex's neighbors — the operation every traversal algorithm does constantly — is exactly as fast as it needs to be, with zero wasted work on non-edges.

The real trade-off is sparsity. Most real-world graphs are sparse (E is much closer to V than to V²) — a social network where each person has hundreds of friends out of a billion users, a road map where each intersection connects to a handful of roads, not every other intersection. For a sparse graph, an adjacency list is dramatically smaller and every traversal is faster because there's nothing to skip over. An adjacency matrix earns its keep only for dense graphs (E close to V²) or when the dominant operation really is "check if this specific edge exists" — for a graph algorithms class or interview, default to adjacency list unless something in the problem specifically calls for O(1) edge lookups or the graph is described as fully or near-fully connected.

Deep Dive: BFS — Level by Level, and Why It Finds Shortest Paths

def bfs(graph, start):
    visited = {start}
    parent = {start: None}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                parent[nb] = node
                q.append(nb)
    return parent

BFS explores a graph one "ring" at a time: visit the start, then every neighbor of the start (distance 1), then every unvisited neighbor of those (distance 2), and so on — a queue enforces this ordering naturally, because FIFO guarantees everything at distance k is dequeued (and its neighbors enqueued, becoming distance k+1) before anything at distance k+1 is dequeued. That's the entire mechanism, and it's exactly why BFS finds shortest paths by number of edges: the first time a vertex is reached, it's necessarily been reached by the fewest possible hops, because BFS exhausts every shorter possibility first.

This only holds when every edge counts the same — an unweighted graph. If edges have different weights (a road map where distances vary), "fewest hops" and "shortest total distance" are different questions, and BFS answers the wrong one: a 1-hop path costing 100 miles would beat a 3-hop path costing 10 miles total under BFS's hop-counting, which is backwards. For weighted graphs (non-negative weights) you need Dijkstra's algorithm instead — see the dedicated Deep Dive below. Precision matters here in an interview: "BFS finds the shortest path" is only true with the unstated assumption "unweighted," and leaving that out is a common, catchable mistake.

Deep Dive: DFS — Go Deep First, and Where It's the Right Tool

def dfs(graph, start):
    visited = {start}
    order = []
    def visit(node):
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                visit(nb)
    visit(start)
    return order

DFS explores as far as possible down one path before backtracking, using either recursion (the call stack does the bookkeeping automatically) or an explicit stack. Where BFS fans out level by level, DFS commits — it follows one neighbor all the way to a dead end, then backs up to the most recent unexplored choice. Run on the same graph as the BFS example above, the visit orders genuinely differ (A,B,C,D,E vs A,B,D,C,E) because DFS's stack-like backtracking and BFS's queue-like level order are fundamentally different traversal disciplines, not just implementation details.

DFS is the right tool whenever the question is about structure rather than distance: does a path exist at all (connectivity), is there a cycle, can this graph be split into independent pieces, what does the full reachable subgraph from a node look like. It's also the natural fit for backtracking problems (maze solving, generating permutations) because "go deep, then undo and try the next option" is exactly DFS's shape. Use BFS specifically when the question involves "shortest," "fewest," or "closest" on an unweighted graph — otherwise DFS is usually simpler to write (especially recursively) and uses less auxiliary memory on a wide, shallow graph.

Deep Dive: Connected Components and Cycle Detection

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nb in graph[node]:
            if color[nb] == GRAY:
                return True
            if color[nb] == WHITE and visit(nb):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)

A connected component is a maximal set of vertices all reachable from each other. Finding all of them is one loop around every vertex: run DFS or BFS from any unvisited vertex, mark everything it reaches as one component, then move to the next unvisited vertex and repeat — each traversal costs no more than the vertices and edges it actually touches, so the whole scan is O(V+E) total, not O(V) traversals of O(V+E) each, because no vertex is ever visited by more than one traversal.

Cycle detection needs a genuinely different check depending on directedness, and conflating them is a common mistake. In an undirected graph, DFS hitting an already-visited neighbor is only a cycle if that neighbor isn't the vertex you just arrived from — otherwise you'd flag every single edge as a "cycle" (you'd immediately re-see the parent you came from, since undirected edges go both ways). In a directed graph, you instead need to know whether the revisited vertex is still on the current DFS path (a 3-color scheme: white = unvisited, gray = on the current path, black = fully explored and off the path) — reaching a gray vertex means you've looped back to an ancestor, a real cycle; reaching a black vertex just means two separate paths converge there, which is completely normal in a DAG and not a cycle at all.

Deep Dive: Topological Sort — Ordering a DAG

def topo_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for nb in graph[node]:
            in_degree[nb] += 1
    q = deque([n for n in graph if in_degree[n] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                q.append(nb)
    return order if len(order) == len(graph) else None

A topological sort is a linear ordering of a directed graph's vertices such that every edge u→v places u before v — "prerequisites before what depends on them." It is only well-defined on a DAG: a cycle means two vertices would each need to come before the other, which is a contradiction no ordering can satisfy, so "does this graph have a valid topological order" and "is this graph acyclic" are the same question. Kahn's algorithm (shown above) makes that fact operational: it repeatedly peels off vertices with no remaining incoming edges, and if it ever runs out of such vertices before processing everyone, whatever's left is stuck in a cycle. The alternative approach, DFS-based topological sort, runs a full DFS and prepends each vertex to the result the moment DFS finishes exploring it (its "postorder") — a vertex is only fully finished after everything it points to is finished, which is exactly the ordering guarantee required.

Topological sort is the algorithm behind resolving build dependencies (compile B before A if A depends on B), spreadsheet recalculation order, course scheduling, and package manager install order. Note that a topological order is not unique in general — data_structures could conceivably be followed by either algorithms or databases first in the walkthrough above; both are valid, since neither depends on the other.

Deep Dive: Weighted Shortest Paths — Why BFS Isn't Enough

Dijkstra's algorithm solves shortest paths on a graph with non-negative edge weights. The core idea is greedy: maintain a running "best known distance" to every vertex (initialized to infinity except the start, which is 0), and repeatedly pick the unvisited vertex with the smallest known distance, "finalize" it (its distance can never improve after this, precisely because all remaining edges are non-negative — nothing left to explore could make a detour through an unvisited vertex cheaper than the direct best-known value), and relax its outgoing edges: for each neighbor, check whether going through the just-finalized vertex beats that neighbor's current best-known distance, and update it if so. Repeating this until every vertex is finalized produces the true shortest distance to each one; a priority queue (see heaps.html) makes "pick the smallest unvisited distance" efficient, giving O((V+E) log V) overall.

Dijkstra breaks down with negative edge weights, because its whole correctness argument rests on "once finalized, a distance can't improve" — a negative edge encountered later could retroactively make an already-finalized vertex's distance too high, and Dijkstra never revisits finalized vertices to fix that. Graphs with negative weights (but no negative cycle) need Bellman-Ford instead, which is slower (O(V·E)) precisely because it re-relaxes every edge repeatedly rather than trusting any vertex as finalized early. This page doesn't implement Dijkstra in full — the point to carry into an interview is precise: BFS for unweighted shortest paths, Dijkstra for weighted non-negative, Bellman-Ford if negative weights are possible.

Key Pointers

• A graph is vertices plus edges; pin down directed vs undirected and weighted vs unweighted first, because they determine which algorithms are even valid.
• Adjacency matrix: O(V²) space, O(1) "does this edge exist," worthwhile mainly for dense graphs. Adjacency list: O(V+E) space, O(degree) edge check, the default for sparse real-world graphs.
• BFS visits level by level via a queue and finds shortest paths by edge count — but ONLY on unweighted graphs; it ignores edge weights entirely.
• DFS goes deep via recursion or an explicit stack; it's the right tool for connectivity, cycle detection, and structural questions rather than shortest distance.
• Connected components: one DFS/BFS per unvisited vertex, O(V+E) total, since no vertex is ever revisited by a second traversal.
• Cycle detection differs by graph type: undirected needs "revisited but not the parent"; directed needs "revisited and still on the current path" (a 3-color DFS).
• Topological sort only exists on a DAG, because a cycle makes "come before" contradictory; Kahn's algorithm (in-degree-0 peeling) both computes it and detects a cycle if it can't finish.
• For weighted non-negative shortest paths, use Dijkstra, not BFS; for possible negative weights, Dijkstra breaks and you need Bellman-Ford.

How It Works

1. Represent the graph: pick adjacency list (sparse, most common) or adjacency matrix (dense, or O(1) edge-existence checks needed), and decide directed vs undirected, weighted vs unweighted.
2. BFS: enqueue the start vertex, mark it visited; while the queue isn't empty, dequeue a vertex, and enqueue+mark every unvisited neighbor. Vertices come out in non-decreasing distance from the start.
3. DFS: visit the start vertex, mark it visited, and recurse (or push to an explicit stack) into each unvisited neighbor before backtracking to try the next one.
4. Connected components: loop over all vertices; for each unvisited one, run a full BFS/DFS from it and mark everything reached as one component.
5. Cycle detection: undirected — DFS, flag a cycle on any visited neighbor that isn't the immediate parent; directed — DFS with a 3-color/on-path marker, flag a cycle on reaching a vertex still marked "on the current path."
6. Topological sort (Kahn's): compute every vertex's in-degree, queue up all in-degree-0 vertices, repeatedly dequeue one, append it to the result, and decrement its neighbors' in-degree, enqueuing any that hit 0.
7. If Kahn's algorithm's result has fewer vertices than the graph, the leftover vertices are on a cycle and no topological order exists.
8. Weighted shortest path: run Dijkstra (non-negative weights) or Bellman-Ford (negative weights allowed, no negative cycle) instead of BFS.

Try It Yourself

BFS and DFS run on the same small graph to show the visit-order contrast, then undirected vs directed cycle detection, then Kahn's algorithm for topological sort (including what it does on a cyclic graph).

from collections import deque

# Undirected graph (small social network), adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}


def bfs(graph, start):
    visited = {start}
    order = []
    parent = {start: None}
    q = deque([start])
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                parent[nb] = node
                q.append(nb)
    return order, parent


def dfs(graph, start):
    visited = {start}
    order = []

    def visit(node):
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                visit(nb)

    visit(start)
    return order


bfs_order, parents = bfs(graph, "A")
print("BFS order from A:", bfs_order)
print("BFS parent pointers:", parents)

dfs_order = dfs(graph, "A")
print("DFS order from A:", dfs_order)


def shortest_path(parent, target):
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    return list(reversed(path))


print("BFS shortest path A->E:", shortest_path(parents, "E"))


# --- Undirected cycle detection ---
def has_cycle_undirected(graph):
    visited = set()

    def visit(node, parent):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                if visit(nb, node):
                    return True
            elif nb != parent:
                return True
        return False

    for node in graph:
        if node not in visited:
            if visit(node, None):
                return True
    return False


no_cycle_undirected = {"A": ["B"], "B": ["A", "C"], "C": ["B"]}
cycle_undirected = {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}

print("undirected, path A-B-C:       has_cycle =", has_cycle_undirected(no_cycle_undirected))
print("undirected, triangle A-B-C-A: has_cycle =", has_cycle_undirected(cycle_undirected))


# --- Directed cycle detection (3-color DFS: white/gray/black) ---
def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def visit(node):
        color[node] = GRAY
        for nb in graph[node]:
            if color[nb] == GRAY:
                return True
            if color[nb] == WHITE and visit(nb):
                return True
        color[node] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE:
            if visit(node):
                return True
    return False


dag = {"A": ["B"], "B": ["C"], "C": []}
directed_cycle = {"A": ["B"], "B": ["C"], "C": ["A"]}

print("directed DAG A->B->C:         has_cycle =", has_cycle_directed(dag))
print("directed cycle A->B->C->A:    has_cycle =", has_cycle_directed(directed_cycle))


# --- Topological sort (Kahn's algorithm, BFS on in-degree) ---
def topo_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for nb in graph[node]:
            in_degree[nb] += 1

    q = deque([n for n in graph if in_degree[n] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                q.append(nb)

    if len(order) != len(graph):
        return None  # cycle present, no valid topological order
    return order


courses = {
    "intro_cs":   ["data_structures"],
    "data_structures": ["algorithms", "databases"],
    "algorithms": ["capstone"],
    "databases":  ["capstone"],
    "capstone":   [],
}
print("topo order (a valid course sequence):", topo_sort_kahn(courses))

broken = {"A": ["B"], "B": ["C"], "C": ["A"]}
print("topo order on a cyclic graph:", topo_sort_kahn(broken))

# Output:
# BFS order from A: ['A', 'B', 'C', 'D', 'E']
# BFS parent pointers: {'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'D'}
# DFS order from A: ['A', 'B', 'D', 'C', 'E']
# BFS shortest path A->E: ['A', 'B', 'D', 'E']
# undirected, path A-B-C:       has_cycle = False
# undirected, triangle A-B-C-A: has_cycle = True
# directed DAG A->B->C:         has_cycle = False
# directed cycle A->B->C->A:    has_cycle = True
# topo order (a valid course sequence): ['intro_cs', 'data_structures', 'algorithms', 'databases', 'capstone']
# topo order on a cyclic graph: None

Notice DFS's order (A, B, D, C, E) genuinely differs from BFS's (A, B, C, D, E) on the exact same graph and start vertex — that's the level-by-level vs go-deep-first contrast made concrete, not asserted. And the cyclic topological sort correctly returns None because Kahn's queue runs dry after processing zero vertices — every vertex in that 3-cycle has in-degree 1, so none ever reaches 0.

Common Mistakes & Interview Traps

• Claiming "BFS finds the shortest path" without the unstated qualifier "on an unweighted graph" — on weighted edges it optimizes hop count, not total cost, which can be a completely different path.
• Using the same cycle-detection logic for directed and undirected graphs — undirected needs to exclude the immediate parent; directed needs to track what's still on the current DFS path (gray), not just "visited at all."
• Forgetting that an undirected edge must be added to both endpoints' adjacency lists — adding only A→B when the intent was "A and B are connected" silently makes the graph directed.
• Running BFS/DFS without a visited set on a graph that has a cycle — the traversal loops forever instead of terminating.
• Assuming a topological order is unique — it usually isn't; any ordering respecting all the edges is valid, and interview answers should say "a valid order," not "the order."
• Reaching for Dijkstra on a graph with negative edge weights — it produces silently wrong answers rather than an error, because its greedy "finalize the smallest known distance" step assumes nothing later can make a finalized vertex cheaper.

Interview Q&A

Q: What's the real trade-off between an adjacency matrix and an adjacency list?

A: An adjacency matrix uses O(V²) space regardless of edge count and gives O(1) "does this exact edge exist," while an adjacency list uses O(V+E) space and gives O(degree) edge checks but O(degree) neighbor listing with zero wasted work. Since most real graphs are sparse (E much less than V²), adjacency list is the default; matrices earn their space cost only for dense graphs or when O(1) edge-existence checks specifically matter.

Q: When does BFS find the shortest path, and when does it NOT (what breaks with weighted edges)?

A: BFS finds the shortest path by edge count on an unweighted graph, because a queue guarantees every vertex at distance k is processed before any vertex at distance k+1. On a weighted graph it still finds the fewest-edges path, but that can be the wrong answer for "cheapest total cost" — a direct 1-hop edge with a huge weight can lose to a 3-hop path with a small total weight, and BFS has no way to notice because it never looks at weights at all.

Q: Walk through BFS and DFS on the same small graph and describe how the visit order differs and why.

A: On the A-B-C-D-E graph in the demo, BFS visits A, B, C, D, E — it exhausts every neighbor of A before going further, because a FIFO queue holds each level's vertices until the previous level is fully processed. DFS visits A, B, D, C, E — it commits to A's first neighbor B, then B's first unvisited neighbor D, then D's first unvisited neighbor C, only backtracking when a path runs out of new vertices. The difference is queue (FIFO, breadth) vs stack/recursion (LIFO, depth).

Q: How do you detect a cycle in a directed graph vs an undirected graph — why is the approach different?

A: Undirected: DFS, and flag a cycle when you reach an already-visited vertex that is not the one you just came from — otherwise every edge would falsely look like a cycle, since undirected edges are bidirectional. Directed: track which vertices are still "on the current DFS path" (a 3-color scheme); reaching a vertex that's on the current path means you've looped back to an ancestor, a genuine cycle, while reaching a vertex that's fully finished and off the path just means two separate paths converge there, which is normal even in an acyclic graph.

Q: What makes a graph eligible for topological sort, and what does the sort actually guarantee?

A: The graph must be a DAG — directed and acyclic. A cycle makes topological order impossible by definition, since two vertices on a cycle would each need to precede the other. The guarantee is that for every edge u→v in the graph, u appears before v in the output order — nothing stronger; the order itself is generally not unique, since independent vertices can appear in either relative order.

Q: What's the core idea behind Dijkstra's algorithm, and why doesn't it work with negative edge weights?

A: Dijkstra greedily finalizes the closest not-yet-finalized vertex, trusting that once a vertex has the smallest known distance among unvisited vertices, nothing left unvisited could offer a cheaper route to it — true only because all remaining edges are non-negative, so a detour can never subtract distance. A negative edge violates that assumption: a path through a not-yet-explored vertex could retroactively beat an already-finalized distance, but Dijkstra never revisits finalized vertices, so it can lock in a wrong answer.

Follow-up: Your graph has negative edge weights but you're told there are no negative cycles — what do you use instead of Dijkstra?

A: Bellman-Ford, which relaxes every edge up to V-1 times rather than trusting any vertex as "finalized" early, at a cost of O(V·E) instead of Dijkstra's O((V+E) log V). It also doubles as a negative-cycle detector: if a V-th round of relaxation can still improve some distance, a negative cycle exists and no shortest path is well-defined for vertices reachable from it.

Follow-up: You need to find if two specific users in a social network are connected at all, not the shortest path between them — would you use BFS, DFS, or something else?

A: Either works identically well for pure reachability — run BFS or DFS from one user and check whether the other was ever visited, both O(V+E). DFS is often the simpler code for this (a single recursive function, no explicit queue), while BFS would additionally hand you the shortest connection path for free if you happened to need that too — pick based on which extra output, if any, you actually need.

Follow-up: Kahn's algorithm on a 10-vertex DAG returns fewer than 10 vertices — what does that mean, and how would you find exactly which vertices are the problem?

A: It means the input graph isn't actually acyclic — some subset of vertices never reached in-degree 0 because they're waiting on each other in a cycle. The vertices missing from the output are precisely those still stuck at in-degree greater than 0 when the queue ran dry; inspecting the in-degree map at that point (or running the directed cycle-detection DFS separately) identifies exactly which vertices form the cycle.

Trade-offs

Graphs are the wrong mental model when a simpler structure already captures the relationships you need — if every relationship is strictly hierarchical with one parent, use a tree and its simpler traversals rather than general graph machinery; if there's no real relationship between items at all, a plain array or hash table is both simpler and faster. Within graph algorithms themselves, the trade-offs are about matching the tool to the question: BFS for unweighted shortest paths (wrong for weighted), DFS for structural questions like connectivity and cycles (unnecessary overhead if all you need is "shortest"), Dijkstra for weighted non-negative shortest paths (silently wrong with negative weights, and slower than BFS when the graph is actually unweighted), Bellman-Ford when negative weights are possible (correct but meaningfully slower than Dijkstra, so don't default to it "just in case"). And representation matters as much as algorithm choice — an adjacency matrix on a large sparse graph wastes both memory and traversal time scanning non-edges that an adjacency list would never touch.

PracticeSolve related problems in the 150 →