Graphs

Why This Matters

Graphs are the language of relationships. Route maps, package dependencies, workflows, knowledge graphs, citation networks, social networks, compilers, and schedulers all become graph problems once you name the vertices and edges.

The hard part is often modeling: the same real system can produce different graphs depending on what an edge means.

Learning Objectives

By the end, you should be able to:

Define vertices, edges, directed graphs, undirected graphs, weighted graphs, and DAGs.
Choose between edge lists, adjacency lists, and adjacency matrices.
Explain when BFS, DFS, topological sort, and connected-component search apply.
Model a real system by deciding what vertices and edges mean.
Connect graph structure to workflows, knowledge graphs, recommendations, and dependency systems.

Core Idea

A graph is G = (V, E): a set of vertices and a set of edges. Edges may be directed or undirected, weighted or unweighted, cyclic or acyclic.

Representation	Space	Edge lookup	Neighbor iteration	Best fit
Edge list	`O(E)`	`O(E)`	`O(E)`	input format, simple scans
Adjacency list	`O(V + E)`	depends on list/set	`O(deg(v))`	sparse graphs
Adjacency matrix	`O(V^2)`	`O(1)`	`O(V)`	dense graphs

Non-Example or Failure Mode

A list of objects is not automatically a graph. A table of users becomes a graph only after you define relationships such as "follows," "messaged," "shares an address," or "belongs to the same organization."

The failure mode is choosing edges before choosing the question. A social graph for friend recommendations, fraud detection, and message routing may need three different edge definitions.

Worked Example

Model a course prerequisite system.

vertices: courses
edge A -> B: course A must be completed before course B

This graph is directed. If it has a cycle, the curriculum is impossible because some course eventually depends on itself. If it is acyclic, a topological sort gives a valid order.

For an unweighted friendship graph, BFS from one person discovers people by distance: friends at distance 1, friends-of-friends at distance 2, and so on.

Builder Connections

Build systems and workflow engines use directed acyclic graphs for execution order.
Knowledge graphs store entity-relation triples and support traversal and retrieval.
Recommendation systems use user-item and item-item graphs.
Compilers use control-flow and dependency graphs.
Data pipelines use graph checks to detect cycles before jobs run.

Common Mistakes

Mistake	Correction
Forgetting edge direction.	A directed edge from A to B does not imply B to A.
Using an adjacency matrix for huge sparse graphs.	Sparse graphs usually need adjacency lists because `O(V^2)` memory is too large.
Treating BFS and DFS as interchangeable.	BFS gives unweighted shortest-path layers; DFS is useful for recursion structure, cycle checks, and finishing times.
Modeling edges before the question.	Define the query or decision first, then choose what an edge means.
Ignoring disconnected components.	Many graph algorithms only explore the component reachable from the chosen start vertex.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What are the vertices and what does an edge mean?	Names both objects and relationship; for example, courses and prerequisite edges.
Example / non-example	Is a spreadsheet dependency graph directed?	Yes. If cell B depends on cell A, the edge has direction from dependency to dependent or vice versa by convention.
Computation	How much memory does an adjacency matrix need for one million vertices?	`10^12` entries before storage overhead, which is usually impossible for sparse graphs.
Proof	Why does BFS find shortest paths in unweighted graphs?	It explores all vertices at distance `d` before any vertex at distance `d + 1`.
Transfer	Why does a workflow orchestrator need cycle detection?	A cycle means some job depends, directly or indirectly, on itself, so no valid execution order exists.

Exercises

Beginner:

Convert the edge list (A, B), (A, C), (B, D) into an adjacency list.
Decide whether a road map should be directed, undirected, or mixed.
Identify connected components in a small undirected graph.

Intermediate:

Run BFS by hand and record discovery layers.
Topologically sort a small prerequisite DAG.

Challenge:

Build a dependency graph for tasks, reject cycles, and return one valid execution order.

Diagram Recommendation

Type: representation comparison plus BFS wavefront.

Caption: "The same graph as an edge list, adjacency list, adjacency matrix, and BFS layers."

Purpose: Connect modeling choices to memory, traversal, and shortest-path behavior.

Implementation Task

Implement a graph with an adjacency list and add BFS.

function bfs(graph: Map<string, string[]>, start: string) {
  const distance = new Map<string, number>([[start, 0]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head += 1) {
    const v = queue[head]!;
    for (const next of graph.get(v) ?? []) {
      if (distance.has(next)) continue;
      distance.set(next, distance.get(v)! + 1);
      queue.push(next);
    }
  }
  return distance;
}

Extend it with cycle detection for directed graphs.

Next Topics

References

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 20-22.
MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.
MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015.
Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 5.