Module P-6·12 min read

Adjacency list vs matrix, directed vs undirected, weighted vs unweighted — the vocabulary every graph algorithm assumes you already know.

Written by Jatin Jain Saraf · Architect of SupraScan

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.

A --- B
|     |
C --- D --- E

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").

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)

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.

Unweighted: A --- B         (every edge costs "1 hop")
Weighted:   A --5-- B       (this specific edge costs 5)

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:

type Graph = Map<string, string[]>;
 
function buildAdjacencyList(edges: [string, string][]): Graph {
  const graph: Graph = new Map();
 
  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] }

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:

function buildAdjacencyMatrix(nodeCount: number, edges: [number, number][]): boolean[][] {
  const matrix = Array.from({ length: nodeCount }, () => new Array(nodeCount).fill(false));
 
  for (const [from, to] of edges) {
    matrix[from][to] = true;
    matrix[to][from] = true; // omit for a directed graph
  }
 
  return matrix;
}