Module P-6 — Introduction to Graphs: Representation and Terminology
What this module covers: A tree (Modules P-4, P-5) has exactly one path between any two nodes and no cycles — it's a special, constrained case. A graph drops those constraints entirely: any node can connect to any other node, cycles are allowed, and there's no single "root." This module covers how graphs are represented in code, the vocabulary every graph algorithm in Module A assumes you already know, and why the representation you choose has real performance consequences.
From Trees to Graphs
Everything about a tree — parent/child direction, no cycles, exactly one path between any two nodes — is a special case. A graph is the general structure: a set of nodes (also called vertices) connected by edges, with no restriction on how many connections a node can have or whether those connections loop back on themselves.
text
This graph has a cycle (A-B-D-C-A) and multiple paths between some pairs of nodes (A to D via B, or via C) — neither is possible in a tree. Trees are graphs with extra rules; graphs don't assume those rules hold.
Directed vs. Undirected
An undirected edge goes both ways — if A connects to B, B connects to A (a friendship, a two-way road). A directed edge has a specific direction — A connects to B doesn't imply B connects to A (a one-way street, a "follows" relationship, a dependency: "A depends on B" doesn't mean "B depends on A").
text
This distinction matters immediately for algorithms: Module A-8 (Topological Sort) only makes sense on a directed graph — "what order should these tasks run in" requires directionality (task A before task B), which an undirected graph has no way to express.
Weighted vs. Unweighted
An unweighted graph treats every edge as equal — the question "how many edges to get from A to B" is what matters, answered by Module A-5's breadth-first search. A weighted graph attaches a cost to each edge — distance, time, price — and the question shifts to "what's the cheapest path from A to B," which is Module A-6's Dijkstra's algorithm, not BFS.
text
Getting this distinction wrong is a real, common bug: running BFS (which assumes every edge costs the same) on a weighted graph can return a path with fewer edges that's actually more expensive than a path with more edges but lower total weight.
Representing a Graph in Code: Adjacency List vs. Adjacency Matrix
Adjacency list — each node maps to a list of its direct neighbors. This is, by far, the more common representation in practice:
typescript
This uses Module F-4's hash map directly — O(1) average lookup for "what are this node's neighbors," and space proportional to the number of edges actually present (O(V + E), vertices plus edges), which matters a great deal on sparse graphs — most real-world graphs (social networks, dependency graphs, road networks) have far fewer edges than the maximum possible n² connections between all node pairs.
Adjacency matrix — a 2D grid where matrix[i][j] indicates whether an edge exists between node i and node j:
typescript
Checking "is there an edge between node i and node j" is O(1) directly — no traversal of a neighbor list required — but the matrix costs O(V²) space regardless of how many edges actually exist, because every possible pair gets a slot whether or not it's connected. On a graph with a million nodes and a few million edges (sparse, realistic for something like a social network), an adjacency matrix would require space for a trillion possible pairs — almost all of them storing false. This is the concrete reason adjacency lists are the default choice, and adjacency matrices are reserved for genuinely dense graphs, or cases where O(1) edge-existence lookups are worth the space trade-off.
Nodes, Edges, Paths, Cycles, Components
A short vocabulary check, since Module A's algorithms all assume it:
Path — a sequence of edges connecting one node to another (A → B → D is a path from A to D in the earlier example).
Cycle — a path that starts and ends at the same node without repeating any edge (A → B → D → C → A).
Connected component — a maximal set of nodes where every node can reach every other node in the set, via some path; a graph can have multiple components that are entirely disconnected from each other. Module A-3 (Union-Find) and Modules A-4/A-5 (DFS/BFS) both directly compute connected components, using different mechanisms.
Degree — the number of edges touching a node (in a directed graph, split further into in-degree and out-degree — edges coming in vs. edges going out — which Module A-8's Kahn's algorithm uses directly).
Where This Shows Up in Your Stack
Social networks: users are nodes, friendships (undirected) or follows (directed) are edges — "mutual friends," "people you may know," and "degrees of separation" are all graph traversal questions, covered directly in Modules A-4 and A-5.
PostgreSQL foreign keys are directed edges between tables — orders.user_id → users.id is a directed relationship, and a full entity-relationship diagram is, structurally, a directed graph.
Dependency graphs: npm packages, microservice call graphs, and build-tool task dependencies are all directed graphs, where a cycle (package A depends on B depends on A) is usually a bug to detect, not a valid state — exactly the problem Module A-8's topological sort with cycle detection solves.
Road networks and routing: cities/intersections are nodes, roads are weighted edges (distance or travel time) — Module A-6's Dijkstra's algorithm is the direct, general-purpose tool for "shortest route from A to B" on exactly this kind of graph.
Summary
A graph generalizes a tree: nodes and edges with no restriction on cycles, multiple paths, or a single root.
Directed edges have a specific direction (A → B doesn't imply B → A); undirected edges go both ways. Algorithms like topological sort only make sense on directed graphs.
Weighted edges carry a cost; unweighted edges treat every connection as equal — using BFS (unweighted-shortest-path logic) on a weighted graph can silently return the wrong answer.
Adjacency lists (a hash map of node → neighbor list) cost O(V + E) space and are the default representation for the sparse graphs most real systems produce.
Adjacency matrices give O(1) edge-existence checks but cost O(V²) space regardless of actual edge count — worth it only for dense graphs or when that specific lookup speed matters more than memory.
Path, cycle, connected component, and degree are the vocabulary every algorithm from here through Module A-9 assumes.
The next module, Backtracking: Exploring the Solution Space, returns to Module P-1's recursion, applied to a new class of problem — systematically exploring every possible choice, and undoing choices that don't pan out.
Knowledge Check
Why can running an unweighted breadth-first search on a weighted graph produce a path that is technically shortest "in number of edges" but not actually the cheapest path?
Why does the module identify adjacency lists as the more common choice for representing real-world graphs like social networks or dependency graphs, compared to adjacency matrices?
According to the module, what specifically distinguishes a directed edge from an undirected edge, and why does this distinction matter for an algorithm like topological sort?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Undirected: A --- B (A can reach B, B can reach A)
Directed: A --> B (A can reach B; whether B can reach A is a separate, unrelated fact)
Unweighted: A --- B (every edge costs "1 hop")
Weighted: A --5-- B (this specific edge costs 5)
typeGraph= Map<string,string[]>;functionbuildAdjacencyList(edges:[string,string][]): Graph {const graph: Graph =newMap();for(const[from, to]of edges){if(!graph.has(from)) graph.set(from,[]);if(!graph.has(to)) graph.set(to,[]);// ensure isolated/leaf nodes still appear as keys graph.get(from)!.push(to); graph.get(to)!.push(from);// omit this line for a directed graph}return graph;}buildAdjacencyList([['A','B'],['A','C'],['B','D'],['C','D']]);// Map { A -> [B, C], B -> [A, D], C -> [A, D], D -> [B, C] }
functionbuildAdjacencyMatrix(nodeCount:number, edges:[number,number][]):boolean[][]{const matrix =Array.from({ length: nodeCount },()=>newArray(nodeCount).fill(false));for(const[from, to]of edges){ matrix[from][to]=true; matrix[to][from]=true;// omit for a directed graph}return matrix;}