Graph Basics and Representations

Intuition

A graph is a set of vertices (nodes) joined by edges. That single abstraction covers road maps, social networks, task dependencies, web links and, the case people forget, grids and puzzle states, where edges are implied by rules instead of being listed.

A few words to use precisely in an interview:

• Directed vs. undirected. A directed edge u -> v can be walked one way only (follows, prerequisites). An undirected edge works both ways (friendship, two-way roads).
• Weighted vs. unweighted. Weights are costs, distances or capacities. Unweighted means every edge costs 1, which is exactly why plain BFS finds shortest paths.
• Degree. The number of edges touching a vertex; in a directed graph, split into in-degree and out-degree. In an undirected graph the degrees sum to 2m (each edge is counted at both ends), so the number of odd-degree vertices is always even.
• Path and cycle. A walk may repeat vertices, a simple path may not, a cycle is a closed path. A directed graph without cycles is a DAG.
• Connected component. A maximal set of vertices that can all reach each other in an undirected graph. Directed graphs have strongly connected components instead.
• Self-loops and parallel edges. An edge from a vertex to itself, or several edges between the same pair. Problems often allow them silently, so ask.
• Sparse vs. dense. With n vertices and m edges, a graph is sparse when m is much smaller than n^2. Most interview graphs are sparse, which is why the adjacency list is the default.
• Tree. A connected undirected graph with n - 1 edges and no cycle.

When to use it in interviews / OAs

Think "graph" whenever the input describes relationships rather than a sequence: pairs like [a, b], "depends on", "can travel from", "is friends with", "differs by one letter", or a 2D board you move across. Before writing code, settle these out loud:

1. Directed or undirected? Weighted? Can weights be negative?
2. How are vertices named: 0..n-1, 1..n, or arbitrary strings?
3. How large are n and m? That decides matrix vs. list, and O(n^3) vs. O((n + m) log n) algorithms.
4. Can the graph be disconnected? Are self-loops or duplicate edges possible?

Template

Three standard representations

Representation	Memory	Edge u-v exists?	Visit neighbors of u	Good for
Edge list	O(m)	O(m)	O(m)	Kruskal, Bellman-Ford, sorting edges
Adjacency matrix	O(n^2)	O(1)	O(n)	Dense graphs, Floyd-Warshall, n up to about 500
Adjacency list	O(n + m)	O(deg u)	O(deg u)	Nearly everything else: BFS, DFS, Dijkstra

from collections import defaultdict

INF = float("inf")


def build_adj(n: int, edges: list[tuple[int, int]], directed: bool = False) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]  # never [[]] * n: that shares one list
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj


def build_weighted_adj(n: int, edges: list[tuple[int, int, int]],
                       directed: bool = False) -> list[list[tuple[int, int]]]:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        if not directed:
            adj[v].append((u, w))
    return adj


def build_matrix(n: int, edges: list[tuple[int, int, int]],
                 directed: bool = False) -> list[list[float]]:
    mat = [[INF] * n for _ in range(n)]
    for i in range(n):
        mat[i][i] = 0
    for u, v, w in edges:
        mat[u][v] = min(mat[u][v], w)  # keep the cheapest of parallel edges
        if not directed:
            mat[v][u] = min(mat[v][u], w)
    return mat


def build_labeled(pairs: list[tuple[str, str]]) -> dict[str, list[str]]:
    # vertices are strings (airports, accounts, words): use a dict of lists
    adj: dict[str, list[str]] = defaultdict(list)
    for u, v in pairs:
        adj[u].append(v)
        adj[v].append(u)
    return adj

Grids are graphs too

A cell (r, c) is a vertex and its in-bounds up/down/left/right cells are its neighbors. Do not build an adjacency list for a grid; generate neighbors on the fly.

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def grid_neighbors(rows: int, cols: int, r: int, c: int):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

Degrees answer more questions than you expect

"Find the town judge" (trusted by everyone else, trusts nobody) or "find the center of a star graph" are degree counting, not traversal:

def find_judge(n: int, trust: list[tuple[int, int]]) -> int:
    # people are 1..n; a pair (a, b) means a trusts b, i.e. an edge a -> b
    score = [0] * (n + 1)
    for a, b in trust:
        score[a] -= 1  # any out-edge disqualifies
        score[b] += 1  # in-edges qualify
    for person in range(1, n + 1):
        if score[person] == n - 1:
            return person
    return -1

Complexity

An adjacency list takes O(n + m) time and memory to build, and a full traversal over it is O(n + m). An adjacency matrix costs O(n^2) no matter how few edges exist: fine for n = 500 (250k cells), hopeless for n = 10^5 (10^10 cells). An edge list is O(m) memory but O(m) per neighbor query, so use it only when the algorithm scans all edges anyway.

Common pitfalls

• Forgetting the reverse edge on undirected input. Symptom: BFS reaches only part of the graph.
• [[]] * n creates n references to one list; every append shows up everywhere.
• Off-by-one labels. The input uses 1..n but you allocated n slots. Allocate n + 1 or subtract 1 when reading, and stay consistent.
• Isolated vertices vanish from a defaultdict graph: a vertex with no edges never becomes a key. Count components by looping over the full vertex range, not over adj.keys().
• Parallel edges overwrite each other in a matrix. Keep the minimum for shortest paths (or add capacities for flow).
• Dense storage by accident. A matrix with n = 10^5 runs out of memory before your algorithm starts.
• Deep recursion. Python's default recursion limit (about 1000) is hit by DFS on a long path; prefer iterative traversal or raise the limit carefully.

Interview variations

• Implicit graphs. Word ladder (words one letter apart), lock combinations, sliding puzzles: neighbors are generated, not stored. Bucketing words by wildcard patterns such as h*t turns O(n^2) pair checks into near-linear work.
• Transpose graph. Reversing every edge answers "who can reach X" with one traversal from X; it is also a step of Kosaraju's SCC algorithm.
• Degree-only questions. Town judge, star center, sources and sinks of a DAG (in-degree or out-degree zero).
• Keep the edge list. When the algorithm sorts edges (Kruskal) or relaxes all of them repeatedly (Bellman-Ford), skip the conversion.
• Trees. n - 1 edges plus connectivity means a tree; pick any root and one traversal gives every parent pointer.