Module 19 · Graph Traversal and Connected Components

181. Build an Adjacency List

Foundation · Download this solution · All solutions and shared helpers

Problem

Convert n vertices numbered 0 through n-1 and valid edge pairs (u,v) into adjacency lists. directed=False adds both directions; directed=True adds only u to v. Preserve input edge order and multiplicity. An undirected self-loop contributes two entries. Isolated vertices still receive empty lists.

Examples

Example 1

adjacency_list(4,[(0,1),(1,2)])
=> [[1], [0, 2], [1], []]

Reverse entries represent undirected edges, including an isolated vertex.

Example 2

adjacency_list(3,[(0,1)],True)
=> [[1], [], []]

Directed edges do not imply a return edge.

Example 3

adjacency_list(1,[(0,0)])
=> [[0, 0]]

An undirected loop contributes both endpoint incidences.

Reveal the worked solution and reasoning

Why this mechanism works

Representation is part of the problem contract. Allocate one independent list per vertex before reading edges, then translate each edge according to directionality. Keeping multiplicity makes this a faithful representation of a multigraph; deduplication would be a separate policy.

State and boundaries

adj[u] contains all neighbor entries contributed by the processed edge prefix for vertex u.

Protocol

Allocate n independent lists.
For each edge append v to adj[u].
If undirected also append u to adj[v].
Return all n lists.

Visualization

edges (0,1),(1,2), n=4
undirected: 0:[1] 1:[0,2] 2:[1] 3:[]
directed:   0:[1] 1:[2]   2:[]  3:[]

Python implementation

def adjacency_list(n, edges, directed=False):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

adjacency_list(4,[(0,1),(1,2)])

L2 adjacency_list: adj = [[] for _ in range(n)]
n=4; edges=[(0, 1), (1, 2)]; directed=False; _=0

L2 adjacency_list: adj = [[] for _ in range(n)]
n=4; edges=[(0, 1), (1, 2)]; directed=False; _=1

L2 adjacency_list: adj = [[] for _ in range(n)]
n=4; edges=[(0, 1), (1, 2)]; directed=False; _=2

L2 adjacency_list: adj = [[] for _ in range(n)]
n=4; edges=[(0, 1), (1, 2)]; directed=False; _=3

L2 adjacency_list: adj = [[] for _ in range(n)]
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[], [], [], []]

L3 adjacency_list: for u, v in edges:
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[], [], [], []]; u=0; v=1

L4 adjacency_list: adj[u].append(v)
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[1], [], [], []]; u=0; v=1

L6 adjacency_list: adj[v].append(u)
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[1], [0], [], []]; u=0; v=1

L3 adjacency_list: for u, v in edges:
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[1], [0], [], []]; u=1; v=2

L4 adjacency_list: adj[u].append(v)
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[1], [0, 2], [], []]; u=1; v=2

L6 adjacency_list: adj[v].append(u)
n=4; edges=[(0, 1), (1, 2)]; directed=False; adj=[[1], [0, 2], [1], []]; u=1; v=2

Result: [[1], [0, 2], [1], []]. Reverse entries represent undirected edges, including an isolated vertex.

adjacency_list(3,[(0,1)],True)

L2 adjacency_list: adj = [[] for _ in range(n)]
n=3; edges=[(0, 1)]; directed=True; _=0

L2 adjacency_list: adj = [[] for _ in range(n)]
n=3; edges=[(0, 1)]; directed=True; _=1

L2 adjacency_list: adj = [[] for _ in range(n)]
n=3; edges=[(0, 1)]; directed=True; _=2

L2 adjacency_list: adj = [[] for _ in range(n)]
n=3; edges=[(0, 1)]; directed=True; adj=[[], [], []]

L3 adjacency_list: for u, v in edges:
n=3; edges=[(0, 1)]; directed=True; adj=[[], [], []]; u=0; v=1

L4 adjacency_list: adj[u].append(v)
n=3; edges=[(0, 1)]; directed=True; adj=[[1], [], []]; u=0; v=1

Result: [[1], [], []]. Directed edges do not imply a return edge.

Why the solution is correct

Initially no processed edge requires an entry. Each iteration adds exactly the one or two entries required for its edge and changes no others. After all edges, every required occurrence is represented, including isolated vertices and repeated edges.

Time and space

O(n+m) time and space for m input edges. Undirected storage has 2m neighbor entries.

Common mistakes

Using [[]]*n aliases every vertex's list. Adding reverse edges to a directed graph changes its reachability.

Reasoning card

State: adj[u] contains all neighbor entries contributed by the processed edge prefix for vertex u.

Invariant: Every input edge appears exactly as required.

Decision to rehearse: Add one or two directions according to the graph contract.

Finish: Return all n lists

Transfer exercise

Store weighted edges as (neighbor,weight) pairs while retaining the same directionality contract.