Graphs & Their Representations: Adjacency List vs Matrix, and the Vocabulary You Need

In plain words

A road map is a graph: cities are vertices, roads between them are edges. Some roads are one-way (directed edges); highways have speed limits or distances (weighted edges); some cities might not be reachable from others (disconnected graph). Any problem that involves things and the connections between them — web pages and links, people and friendships, tasks and dependencies, molecules and bonds — is naturally a graph problem. Once you see the graph, a rich library of algorithms (traversal, shortest paths, spanning trees) falls into place.

A tree was a graph with training wheels: one root, one parent per node, no cycles. Remove those restrictions — let any node connect to any others, allow cycles, allow disconnected pieces — and you get the graph, the most general and most widely applicable structure in the course. Road maps, social networks, the web's link structure, dependency graphs in build systems, state machines, molecule structures, task scheduling — all graphs. Recognizing that a problem *is* a graph problem is often the hardest and most valuable step; the algorithms that follow (BFS/DFS, shortest paths, MSTs) are comparatively mechanical.

Vocabulary

A graph G = (V, E) is a set of vertices (nodes) V and a set of edges E connecting pairs of them. Throughout the graph lessons, V and E mean the *counts* of vertices and edges — the two variables every graph complexity is written in. The key distinctions:

• Directed vs undirected. An undirected edge {u, v} is mutual (friendship, a two-way road). A directed edge (u → v) is one-way (a Twitter follow, a one-way street, 'A must run before B'). Directedness changes everything downstream.
• Weighted vs unweighted. A weight on each edge represents distance, cost, time, or capacity. Unweighted graphs implicitly weight every edge 1 — which is exactly why BFS finds shortest paths on them.
• Cyclic vs acyclic. A cycle is a path returning to its start. A directed graph with no cycles is a DAG (directed acyclic graph) — the structure behind scheduling, dependency resolution, and topological sort.
• Connected vs disconnected. An undirected graph is connected if every vertex is reachable from every other; otherwise it splits into connected components. (Directed graphs have the stronger notion of *strongly* connected components.)
• Degree. The number of edges at a vertex — split into in-degree and out-degree for directed graphs. Dense means E is near its V² maximum; sparse means E is closer to V. This one property decides your representation.

Undirected graph (4 cities, 4 roads):
    A ─── B
    |     |
    C ─── D

Directed graph (one-way streets):
    A ──► B
    ▲     │
    │     ▼
    C ◄── D

Weighted directed graph (flight distances):
    A ──350──► B
    ▲          │
    │         500
   200         ▼
    C ◄──150── D

DAG (task dependencies, "must finish before"):
    A ──► B ──► D
    │           ▲
    └──► C ─────┘
(No cycles: valid topological order exists: A, B, C, D)

Disconnected graph (two components):
    A ─── B     C ─── D
    (A,B can't reach C,D)

The two representations

Adjacency list

Store, for each vertex, a list of its neighbors (with weights, if weighted). Concretely: an array indexed by vertex, each slot holding a list of adjacent vertices. Total space is O(V + E) — one entry per vertex plus one entry per edge (two for undirected, since each edge appears in both endpoints' lists). This is the default representation, because it stores only edges that actually exist and lets you iterate a vertex's neighbors in time proportional to its degree.

Adjacency matrix

Store a V × V grid where cell [u][v] is 1 (or the edge weight) if an edge u→v exists, else 0 (or infinity). Space is O(V²) *regardless of how many edges exist* — a graph with 10,000 vertices and 5 edges still allocates 100 million cells. The payoff: checking 'is there an edge from u to v?' is a single O(1) array lookup, and the dense mathematical structure suits certain algorithms and hardware-accelerated linear algebra.

Graph: A─B, A─C, B─D (undirected, 4 vertices, 3 edges)

Adjacency LIST (default):
  A: [B, C]
  B: [A, D]
  C: [A]
  D: [B]

Space: 4 vertices + 6 list entries (2 per undirected edge) = O(V+E)
Iterate A's neighbors: O(degree(A)) = O(2)  ← fast

Adjacency MATRIX (A=0, B=1, C=2, D=3):
       A  B  C  D
  A  [ 0  1  1  0 ]
  B  [ 1  0  0  1 ]
  C  [ 1  0  0  0 ]
  D  [ 0  1  0  0 ]

Space: 4×4 = 16 cells = O(V²)
Is there edge A→B? matrix[0][1] = 1  ← O(1)
Iterate A's neighbors: scan row A → O(V) = O(4)  ← slower

For V=1,000,000 vertices with E=2,000,000 edges:
  List:   ~3M entries (feasible)
  Matrix: 10^12 entries (impossible)

The trade-off, quantified

The decisive rows are space and neighbor-iteration, because graph traversal — the heart of nearly every graph algorithm — visits every vertex and walks its neighbors. On an adjacency list that's O(V + E); on a matrix it's O(V²), which is dramatically worse for sparse graphs. Since real graphs (road networks, social graphs, web links) are overwhelmingly sparse — each vertex connects to a tiny fraction of all others — the adjacency list is the right default. Reach for the matrix only when the graph is genuinely dense, when V is small, or when O(1) edge-existence checks dominate your workload.

Adding weights

Weighted graph: A─(5)─B, A─(2)─C, B─(8)─D

Adjacency list (each entry is a (neighbor, weight) pair):
  A: [(B, 5), (C, 2)]
  B: [(A, 5), (D, 8)]
  C: [(A, 2)]
  D: [(B, 8)]

Weighted adjacency matrix (∞ = no edge):
       A    B    C    D
  A  [ 0    5    2    ∞ ]
  B  [ 5    0    ∞    8 ]
  C  [ 2    ∞    0    ∞ ]
  D  [ ∞    8    ∞    0 ]

For Dijkstra's algorithm, the adjacency LIST is standard:
  push (source, dist=0) onto priority queue
  for each neighbor (v, w) of current vertex u:
      new_dist = dist[u] + w
      if new_dist < dist[v]: update + push

Modeling problems as graphs

The real skill is *seeing* the graph. Ask: what are my vertices (the things), what are my edges (the relationships), are edges directed, are they weighted? Some translations that recur constantly:

• A grid/maze → vertices are cells, edges connect adjacent walkable cells. Shortest path through a maze is BFS on this implicit graph — you often never build the graph explicitly, just compute neighbors on the fly.
• Course prerequisites / build dependencies → vertices are tasks, directed edges are 'must come before'. A valid order exists iff the graph is a DAG; finding it is topological sort.
• Word ladders / state puzzles → vertices are states (words, board configurations), edges are legal single moves. 'Fewest moves' becomes shortest path.
• Social/recommendation networks → vertices are people/items, edges are relationships; components, distances, and centrality all become graph queries.
• Currency exchange, network flow, task assignment → weighted and directed graphs feeding shortest-path, max-flow, and matching algorithms.

Worked example: building an adjacency list

Model an undirected road network: cities A, B, C, D with roads A–B, A–C, B–D. As an adjacency list: A → [B, C]; B → [A, D]; C → [A]; D → [B]. Each undirected edge appears twice (once per endpoint), so 3 edges yield 6 list entries — that's the '2E for undirected' rule. Space used: 4 vertices + 6 entries = O(V + E). The matrix version would be a 4×4 grid of 16 cells, mostly zeros. Even on this tiny sparse graph the list is leaner, and the gap explodes at scale: a million-vertex road map is trivial as a list and utterly impossible (10¹² cells) as a matrix.

// Build adjacency list from edge list
function buildGraph(V, edges, directed=false):
    adj = array of V empty lists
    for (u, v) in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)   // undirected: add both directions
    return adj

// Example:
// V=4, edges=[(0,1),(0,2),(1,3)], directed=false
// adj[0]=[1,2], adj[1]=[0,3], adj[2]=[0], adj[3]=[1]

// For weighted graphs: adj[u].append((v, weight))

Common pitfalls

• Adding an undirected edge only once. Undirected edges must be inserted into *both* endpoints' lists. Forgetting the second insert silently makes the graph directed and breaks traversals.
• Defaulting to an adjacency matrix. The intuitive grid wastes O(V²) memory and makes traversal O(V²). Unless the graph is dense or tiny, use a list.
• Ignoring disconnected components. A traversal from one vertex only reaches its component. To cover the whole graph (e.g., count components), loop over all vertices and start a fresh traversal from each unvisited one.
• Confusing directed and undirected reachability. In a directed graph, u reaching v does not imply v reaches u. Many bugs come from assuming symmetry that isn't there.
• Not tracking visited vertices. Graphs have cycles; a traversal without a visited-set loops forever. (The next lesson makes this the central discipline.)

Practice problems

1. Count connected components. Given an undirected graph as an adjacency list, count how many connected components it has. Iterate over all unvisited vertices and start a BFS/DFS from each; the number of times you start a new traversal is the component count.
2. Detect a cycle in a directed graph. Using DFS with three-color marking (white/gray/black for unvisited/in-progress/done), detect if any back edge exists. A back edge from a gray node to another gray node proves a cycle.
3. Model a word-ladder puzzle. Given a start word, end word, and dictionary, find the shortest transformation sequence where each step changes one letter. Vertices = words, edges = pairs of words differing by one letter. Apply BFS; the BFS distance from start to end is the answer.

Key takeaways

• A graph is vertices + edges, generalizing trees by allowing cycles, disconnection, direction, and weights.
• Adjacency list: O(V + E) space, neighbor iteration in O(degree) — the default for sparse (i.e., most) graphs.
• Adjacency matrix: O(V²) space, O(1) edge checks — for dense or small graphs, or lookup-heavy workloads.
• Every graph complexity is written in V and E; know your graph's density before choosing a representation.
• The hard part is modeling: identify vertices, edges, direction, and weight, and the standard algorithms fall into place.

With a graph in memory, the first thing you'll want to do is explore it. Next: the two fundamental traversals every graph algorithm builds on — breadth-first and depth-first search. Practice graph-modeling questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play