A graph is nodes plus connections between them — no strict hierarchy required, unlike a tree. Trees, in fact, are just graphs with no cycles. Before you can run BFS/DFS (Phase 7), you need to pick how to store the graph, and that choice has real time/space consequences.

What you’ll learn

• The three standard representations: adjacency list, adjacency matrix, edge list.
• Directed vs undirected, and weighted vs unweighted graphs.
• Time/space tradeoffs for each representation, and when to pick which.
• Building a graph from raw edge input — the step every graph problem starts with.

The same small graph, three ways

Take this undirected graph with 4 nodes and 4 edges:

  graph LR
    N0((0)) --- N1((1))
    N0 --- N2((2))
    N1 --- N2
    N2 --- N3((3))

1. Adjacency list — a dict of lists

Store, for each node, the list of nodes it connects to. This is the default choice for almost all graph algorithms — compact, and iterating a node’s neighbors is directly proportional to how many neighbors it actually has.

from collections import defaultdict
 
# Undirected: each edge is added BOTH ways
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # remove this line for a DIRECTED graph
 
print("adjacency list:")
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")
 
print("neighbors of 2:", graph[2])

from collections import defaultdict
 
# Undirected: each edge is added BOTH ways
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # remove this line for a DIRECTED graph
 
print("adjacency list:")
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")
 
print("neighbors of 2:", graph[2])

2. Adjacency matrix — an n x n grid

Store an n x nn x n grid where matrix[u][v] = 1matrix[u][v] = 1 (or a weight) if an edge exists between uu and vv, else 00. Checking “are uu and vv connected?” is $O(1)$, but the matrix costs $O(n^2)$ space regardless of how many edges actually exist.

n = 4   # number of nodes, labeled 0..3
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1   # remove this line for a DIRECTED graph
 
print("adjacency matrix:")
for row in matrix:
    print(" ", row)
 
print("0 and 2 connected?", matrix[0][2] == 1)
print("0 and 3 connected?", matrix[0][3] == 1)

n = 4   # number of nodes, labeled 0..3
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1   # remove this line for a DIRECTED graph
 
print("adjacency matrix:")
for row in matrix:
    print(" ", row)
 
print("0 and 2 connected?", matrix[0][2] == 1)
print("0 and 3 connected?", matrix[0][3] == 1)

3. Edge list — a flat list of pairs

Just the raw list of (u, v)(u, v) pairs, with no lookup structure at all. Cheapest to build and to store, but finding a node’s neighbors means scanning every edge — $O(E)$ per query.

edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
def neighbors_of(edges, target, directed=False):
    result = []
    for u, v in edges:
        if u == target:
            result.append(v)
        elif not directed and v == target:
            result.append(u)
    return result
 
print("edge list:", edges)
print("neighbors of 2 (scan every edge):", neighbors_of(edges, 2))

edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
 
def neighbors_of(edges, target, directed=False):
    result = []
    for u, v in edges:
        if u == target:
            result.append(v)
        elif not directed and v == target:
            result.append(u)
    return result
 
print("edge list:", edges)
print("neighbors of 2 (scan every edge):", neighbors_of(edges, 2))

Edge lists show up mostly as the input format for a problem (e.g. “you are given edgesedges, a list of [u, v][u, v] pairs”) — you almost always convert them into an adjacency list before running any real algorithm on them.

Directed vs undirected, weighted vs unweighted

• Undirected: an edge (u, v)(u, v) means you can travel u -> vu -> v and v -> uv -> u. Add the connection both ways (as in the adjacency list/matrix code above).
• Directed: an edge (u, v)(u, v) only means u -> vu -> v. Add the connection one way only — this is the “remove this line” comment in the code above.
• Weighted: each edge carries a cost, not just a yes/no connection. In an adjacency list, store (neighbor, weight)(neighbor, weight) pairs instead of bare neighbors; in a matrix, store the weight instead of 11.

from collections import defaultdict
 
# Directed, weighted: edges are (source, destination, weight)
weighted_edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 5)]
 
graph = defaultdict(list)
for u, v, w in weighted_edges:
    graph[u].append((v, w))   # directed: only u -> v, carrying weight w
 
print("weighted, directed adjacency list:")
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")
 
# cost of going straight from 0 to 2
for neighbor, weight in graph[0]:
    if neighbor == 2:
        print("cost 0 -> 2:", weight)

from collections import defaultdict
 
# Directed, weighted: edges are (source, destination, weight)
weighted_edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 5)]
 
graph = defaultdict(list)
for u, v, w in weighted_edges:
    graph[u].append((v, w))   # directed: only u -> v, carrying weight w
 
print("weighted, directed adjacency list:")
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")
 
# cost of going straight from 0 to 2
for neighbor, weight in graph[0]:
    if neighbor == 2:
        print("cost 0 -> 2:", weight)

Building a graph from raw edge input

This is the very first step of nearly every graph problem: you’re handed nn (number of nodes) and edgesedges (a list of pairs), and you build an adjacency list before doing anything else.

from collections import defaultdict
 
 
def build_graph(n, edges, directed=False):
    graph = defaultdict(list)
    for node in range(n):
        graph[node]   # ensure every node 0..n-1 has an entry, even isolated ones
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph
 
 
n = 5
edges = [(0, 1), (1, 2), (3, 4)]   # node 4 has no edges to node 0-2 -- two components
 
graph = build_graph(n, edges)
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")

from collections import defaultdict
 
 
def build_graph(n, edges, directed=False):
    graph = defaultdict(list)
    for node in range(n):
        graph[node]   # ensure every node 0..n-1 has an entry, even isolated ones
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph
 
 
n = 5
edges = [(0, 1), (1, 2), (3, 4)]   # node 4 has no edges to node 0-2 -- two components
 
graph = build_graph(n, edges)
for node in sorted(graph):
    print(f"  {node}: {graph[node]}")

Complexity at a glance

VV = number of vertices, EE = number of edges, deg(u)deg(u) = degree (neighbor count) of node uu.

Where this leads: BFS/DFS in Phase 7

Every graph traversal — BFS (shortest path in unweighted graphs), DFS (cycle detection, connected components, topological sort) — is built directly on top of the adjacency list from this lesson: “for each neighbor of the current node, do X.” Getting the representation right here is what makes those algorithms a few lines of code instead of a mess of index arithmetic.

LeetCode problem set

Both of these are traversal problems — the topic right after this one once BFS/DFS are introduced.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1791 — Find Center of Star Graph · Easy

Problem. A star graph has one centre connected to every other node. Given its edge list, return the centre.

Constraints. 3 <= n <= 10^53 <= n <= 10^5, exactly n - 1n - 1 edges, and the input is guaranteed to be a valid star.

Examples. [[1,2],[2,3],[4,2]][[1,2],[2,3],[4,2]] gives 22 · [[1,2],[5,1],[1,3],[1,4]][[1,2],[5,1],[1,3],[1,4]] gives 11

LC 997 — Find the Town Judge · Easy

Problem. In a town of nn people, the judge trusts nobody, everybody else trusts the judge, and there is at most one judge. Given trusttrust pairs [a, b][a, b] meaning aa trusts bb, return the judge’s label or -1-1.

Constraints. 1 <= n <= 10001 <= n <= 1000, 0 <= len(trust) <= 10^40 <= len(trust) <= 10^4, pairs are distinct.

Examples. n = 2, trust = [[1,2]]n = 2, trust = [[1,2]] gives 22 · n = 3, trust = [[1,3],[2,3]]n = 3, trust = [[1,3],[2,3]] gives 33 · n = 3, trust = [[1,3],[2,3],[3,1]]n = 3, trust = [[1,3],[2,3],[3,1]] gives -1-1

LC 133 — Clone Graph · Medium

Problem. Given a reference to a node in a connected undirected graph, return a deep copy. Each node has a valval and a list of neighborsneighbors.

Constraints. 0 <= number of nodes <= 1000 <= number of nodes <= 100, values are unique, the graph has no self-loops or repeated edges and is connected.

Examples. The square 1-2-3-4-11-2-3-4-1 must be copied so that the structure matches and no node object is shared with the original.

Recap

• Adjacency list ($O(V+E)$ space): the default, best for iterating a node’s neighbors — what nearly every graph algorithm expects.
• Adjacency matrix ($O(V^2)$ space): $O(1)$ edge checks, worth it only for dense graphs or frequent direct-connection queries.
• Edge list ($O(E)$ space): the common input format, converted to an adjacency list before real work starts.
• Undirected = add both directions; directed = add one; weighted = carry a value alongside each neighbor.
• Always pre-seed nodes 0..n-10..n-1 so isolated nodes aren’t silently dropped.

Next up in Phase 7: BFS and DFS run directly on the adjacency list built here — shortest paths, connected components, and cycle detection.