217: Graph Representation, BFS, DFS, Components, and Cycle Detection

Learning outcomes

By the end of this lesson, you can:

explain and apply adjacency list in a realistic implementation;
explain and apply adjacency matrix in a realistic implementation;
explain and apply bfs in a realistic implementation;
explain and apply dfs in a realistic implementation;
explain and apply connected components in a realistic implementation.

You should also be able to state the assumptions behind each implementation: whether edges are directed, whether they carry weights, whether duplicate edges or self-loops are valid, and what result should be returned for an invalid start vertex. Those details are part of the algorithm's contract, not incidental implementation choices.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from your previous projects where the same concern appeared. Perhaps you had to model links between records, dependencies between jobs, routes between services, or permissions between entities. The domain does not need to have been called a graph for the underlying relationship to be graph-shaped.

The goal is not to memorize terminology. It is to make a defensible decision inside an interview-sized problem and a production data-processing problem. Start from the constraints: what is a vertex, what is an edge, which direction does the relationship have, and what operation must be fast? The learner must reason from those constraints rather than memorize a template.

Terminology

Adjacency list: Adjacency lists store neighbors per vertex and use O(V+E) space, making them the default for sparse graphs and traversal algorithms. The list for a vertex contains the edges that leave it; for an undirected graph, each edge is normally stored in both endpoint lists.
Adjacency matrix: A VxV matrix offers O(1) edge lookup but O(V²) space, suitable for dense/small graphs or algorithms that benefit from matrix access. The entry at row u, column v records whether an edge exists, or may hold its weight or another edge value.
BFS: Breadth-first search explores by increasing edge count and therefore yields shortest path length in unweighted graphs. Its queue processes the frontier in layers: vertices one edge away, then two edges away, and so on.
DFS: Depth-first search explores deeply and supports components, cycle detection, topological reasoning, articulation-style ideas, and backtracking. It follows one branch as far as possible before returning to a previous decision point.
Connected components: Restart traversal from every unvisited vertex to label components in undirected graphs; directed connectivity has distinct weak/strong definitions. In a directed graph, merely using the undirected definition can answer the wrong question.
Cycle detection: Undirected DFS distinguishes the parent edge; directed DFS tracks recursion-stack/color state. The same “visited” flag is not enough for both cases because reaching an already visited vertex has different meanings depending on direction and traversal state.

Mental model

Treat Graph Representation, BFS, DFS, Components, and Cycle Detection as a design problem with observable inputs, outputs, invariants, and failure modes. Graphs generalize relationships beyond trees: a vertex can have many neighbors, a graph can be disconnected, and a path can return to a vertex that was already encountered. Before choosing an algorithm, define direction, weights, connectivity, density, and whether parallel/self edges are allowed. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

For example, “find the nearest server” suggests BFS only if every edge has equal cost. If links have different latencies, edge count is not the same as travel cost, and a weighted shortest-path algorithm is a different choice. Likewise, “is this dependency graph safe?” requires a directed-cycle interpretation, not an undirected one. These distinctions prevent a correct algorithm from being applied to the wrong model.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. During implementation, keep the representation and traversal contract visible: a neighbor lookup should not silently change direction, and a traversal should not silently revisit the same vertex without a reason.

Deep dive

1. Adjacency list

Suppose a graph has many possible vertex pairs but only a small number of actual relationships. An adjacency matrix allocates space for all those possible pairs, including the ones that do not exist. An adjacency list stores the neighbors that are actually present, so it uses O(V+E) space and is usually the default for sparse graphs and traversal algorithms.

Adjacency lists store neighbors per vertex and use O(V+E) space, making them the default for sparse graphs and traversal algorithms. A traversal visits each reachable vertex and examines each stored edge, so a full BFS or DFS is typically O(V+E) when the graph is represented this way. For an undirected graph, storing both directions is what lets traversal move from either endpoint; it also means the input contains two adjacency entries for one logical edge.

The representation should make invalid states difficult to express. In the TypeScript example below, vertex IDs are array indexes, so the caller must either validate IDs at the boundary or accept that an out-of-range lookup is invalid. If the graph arrives from JSON, compile-time types do not perform that validation at runtime.

Decision rule: Use adjacency list deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Ask whether neighbor iteration is the dominant operation, whether the graph is sparse, and whether the order of neighbors has observable consequences for deterministic output.

2. Adjacency matrix

When the main question is “does an edge from u to v exist?”, a matrix is direct. The cell at [u][v] can answer that lookup in O(1), without scanning a neighbor collection. This is useful for dense or small graphs, and for algorithms whose inner loop naturally considers every possible pair.

A VxV matrix offers O(1) edge lookup but O(V²) space, suitable for dense/small graphs or algorithms that benefit from matrix access. Traversing from one vertex with a matrix usually requires scanning an entire row, including absent edges, so a sparse graph can make traversal cost approach O(V²). That is the central trade-off: faster arbitrary edge lookup in exchange for memory proportional to every possible pair.

For an undirected graph, the matrix is normally symmetric: setting [u][v] also sets [v][u]. A directed graph does not have that requirement. A weighted matrix needs an unambiguous value for “no edge”; using 0 is unsafe if a zero-weight edge is valid, so a sentinel such as Infinity or a separate presence structure may be clearer.

Decision rule: Use adjacency matrix deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Confirm that V is small enough for O(V²) memory and that constant-time edge lookup is worth scanning or allocating the full matrix.

3. BFS

When a problem asks for the fewest number of unweighted hops, the useful property is not merely that BFS “uses a queue.” Breadth-first search explores by increasing edge count and therefore yields shortest path length in unweighted graphs. The first time a vertex is discovered, the route used to discover it has the minimum possible number of edges from the start.

Mark visited when enqueuing to avoid duplicate queue growth. In a distance-based implementation, assigning a distance other than -1 is the visited mark. If marking waits until dequeue time, several parents can enqueue the same vertex before the first copy is processed. The result may still be recoverable, but the queue can grow unnecessarily and the shortest-distance invariant becomes harder to reason about.

The BFS invariant is: every enqueued vertex has a known shortest distance from start, and the queue is processed in nondecreasing distance order. The algorithm gives shortest edge count, not lowest weighted cost. It also reaches only the connected portion of the graph from the chosen start; a separate restart is needed to cover all components.

Decision rule: Use bfs deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Choose it for unweighted shortest paths, level-order exploration, and nearest qualifying vertices. State what “nearest” means before using it.

4. DFS

DFS is useful when the question depends on completing one branch before moving to another. Depth-first search explores deeply and supports components, cycle detection, topological reasoning, articulation-style ideas, and backtracking. Its core invariant is that a vertex is explored through its outgoing neighbors before the traversal returns from that vertex.

Recursive DFS expresses that shape naturally, but recursive DFS has depth limits. A long chain can exceed the call stack even though the graph algorithm itself is valid. An iterative version with an explicit stack avoids that particular runtime limit, although the stack still uses O(V) worst-case space. The order of results can also differ based on whether neighbors are pushed in their original order or reverse order.

Decision rule: Use dfs deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Use it for reachability, exhaustive exploration, components, cycle checks, and backtracking, while making recursion depth and traversal order explicit.

5. Connected components

A single traversal from one start vertex answers reachability from that vertex. It does not tell you how many disconnected groups exist. Restart traversal from every unvisited vertex to label components in undirected graphs; directed connectivity has distinct weak/strong definitions.

The outer loop supplies the missing piece: when it finds an unvisited vertex, that vertex starts a new component, and BFS or DFS marks every vertex in that component. The total work remains O(V+E) with an adjacency list because each vertex is started at most once and each stored edge is examined a bounded number of times. For directed graphs, clarify whether “connected” means weakly connected after ignoring direction or strongly connected, where every vertex can reach every other through directed paths.

Decision rule: Use connected components deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Name the connectivity definition in the API or documentation instead of returning a plausible-looking answer with ambiguous semantics.

6. Cycle detection

Cycle detection is where graph direction matters most. In an undirected DFS, seeing a visited neighbor does not automatically prove a cycle, because the edge back to the vertex's parent is expected. Undirected DFS distinguishes the parent edge; a visited neighbor other than the parent indicates another route back into the explored structure.

Directed DFS tracks recursion-stack/color state. A common three-state model is white for unvisited, gray for currently active, and black for completely processed. An edge to a gray vertex points back into the active path and proves a directed cycle. An edge to a black vertex does not, by itself, prove a cycle in the current path.

Disjoint-set can detect cycles incrementally in undirected edge streams. Before unioning an edge (u, v), find the representative of each endpoint. If they are already the same, the new edge closes a cycle; otherwise union the sets. This is useful for an edge stream, but it does not replace directed DFS cycle detection and does not provide the same traversal information.

Decision rule: Use cycle detection deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Specify whether self-loops count as cycles and whether parallel edges are legal, because both choices affect the expected result.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. For example, “return the minimum number of unweighted edges from a valid start vertex to every reachable vertex” is a more useful requirement than simply “run BFS.”

The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but makes edge cases much harder to reason about. A graph algorithm should receive a validated model, or its contract should explicitly define how malformed vertices and edges are handled.

type Edge = readonly [to: number, weight: number];
type Graph = readonly Edge[][];

function bfs(graph: Graph, start: number): number[] {
  const distance = Array(graph.length).fill(-1);
  const queue = [start];
  distance[start] = 0;
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i]!;
    for (const [next] of graph[node]!) {
      if (distance[next] !== -1) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }
  return distance;
}

The weight field is present in the edge type, but this BFS intentionally ignores it. That is safe only when the problem defines every edge as having equal cost. If weights represent different travel costs, the function returns minimum hop counts, not minimum total weights; changing the type without changing the algorithm would create a misleading API.

The array initialized to -1 serves two purposes: it records that a vertex has not been reached, and it stores the shortest known distance once the vertex is discovered. The loop index is used instead of removing items from the front of the array, so queue processing remains efficient. The non-null assertions communicate an assumption to TypeScript, not a runtime check. In production input, validate start, each next, and the shape of every adjacency entry before relying on those assumptions.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this graph-specific example, make those concrete: use a reachable path, a graph with no vertices or an invalid start, repeated edges or a self-loop, and malformed or unavailable graph data. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

For a normal path, the expected result contains nonnegative distances for reachable vertices and -1 for vertices outside the start's reachable region. For a duplicate edge, the first discovery marks the destination, so the duplicate does not enqueue another copy. For a self-loop, the vertex is already marked, so BFS does not change its distance; whether the self-loop should be reported as a cycle belongs to the cycle-detection contract, not to this distance calculation. An invalid start must be rejected or represented by a documented error before indexing the graph. If graph data comes from a dependency, the boundary should distinguish unavailable data from a valid empty graph rather than silently converting one into the other.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

For graph workloads, high cardinality changes the representation decision quickly. An O(V²) matrix can become impossible even when a list-based traversal is straightforward. A traversal over a very deep graph may also exhaust a recursive call stack, and an unexpectedly dense graph can make the queue or visited state large. Measure vertex and edge counts, traversal duration, memory pressure, and failure rates rather than assuming that the asymptotic label alone describes operational behavior.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A graph received from a client should not be trusted merely because its JSON shape resembles the TypeScript type.

Guided lab

Represent the same graph as list and matrix, implement iterative BFS/DFS, count components, and detect cycles in both undirected and directed graphs. Test disconnected and self-loop cases. Keep the graph small enough to inspect by hand first, then add a case that exposes the chosen representation's trade-off.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

As you work, record whether the graph is directed and whether each edge is weighted. Use the same vertices and logical edges in the list and matrix versions, then compare the answers. For BFS and DFS, inspect the visited state and traversal order. For components, verify that restarting from unvisited vertices finds every group. For cycle detection, test an undirected parent edge, an undirected self-loop, a directed back edge, and a directed acyclic graph; these cases expose the distinctions that a single happy-path graph hides.

Edge cases and failure modes

Adjacency list: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also verify whether undirected edges are represented in both directions, whether a self-loop is accepted, and whether a missing vertex has an empty neighbor list or is an error.
Adjacency matrix: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check row lengths, symmetry for undirected graphs, the sentinel for “no edge,” and the memory consequence of increasing V.
BFS: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include an invalid start, a disconnected target, repeated edges, a self-loop, and weighted edges to confirm that the contract is minimum hop count rather than minimum total weight.
DFS: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include a very deep chain to expose recursion limits, and make traversal-order assumptions explicit if callers compare output sequences.
Connected components: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Test an empty graph, isolated vertices, one connected graph, several components, and directed input under both weak and strong connectivity definitions when those definitions matter.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

Graph-specific mistakes are often contract mistakes in disguise: using BFS for weighted shortest paths, treating a directed graph as undirected, counting the parent edge as an undirected cycle, or forgetting to restart traversal for disconnected components. Another common failure is marking a vertex too late in BFS, which creates duplicate queue entries and obscures the distance invariant.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Log or inspect the vertex and edge counts, representation, direction setting, start vertex, visited state, and queue or stack behavior. Compare a failing result with a hand-worked graph whose expected distances, component labels, or cycle status are known.

Interview questions

What problem does Adjacency list solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Adjacency matrix solve, and what trade-off or failure mode would make you choose a different approach?
What problem does BFS solve, and what trade-off or failure mode would make you choose a different approach?
What problem does DFS solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Connected components solve, and what trade-off or failure mode would make you choose a different approach?

When answering, include the relevant invariant and complexity rather than naming only a data structure. A strong answer also says when the assumption breaks: BFS needs equal edge costs for shortest-hop reasoning, a matrix needs acceptable O(V²) storage, recursive DFS has depth limits, and component or cycle semantics depend on direction.

Checkpoint

Without notes, explain Graph Representation, BFS, DFS, Components, and Cycle Detection to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Your explanation should make the model testable. State what a vertex and edge mean, how direction is represented, how an unvisited vertex is marked, and what the returned distance, component label, or cycle result means. If you cannot state those contracts, the implementation is not ready to review.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.