Adjacency List

Graph Representation: Adjacency List

A graph is a set of nodes (vertices) connected by edges. The adjacency list is the most common representation — a dictionary mapping each node to its list of neighbors.

Graph:    0 — 1
          |   |
          2 — 3

Adjacency list:
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}

Why Adjacency List?

• Space: O(V + E) — much better than a matrix for sparse graphs
• Iteration: O(degree) to iterate a node's neighbors
• Check edge: O(degree) — use a set of neighbors for O(1)

Building from Edges

def build_graph(n, edges):
    graph = {i: [] for i in range(n)}   # n nodes: 0..n-1
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)              # undirected
    return graph

Directed vs Undirected

# Directed: only one direction
graph[u].append(v)

# Undirected: both directions
graph[u].append(v)
graph[v].append(u)

Your Task

Implement build_graph(n, edges) that creates an undirected adjacency list for a graph with n nodes (labeled 0 to n-1) from a list of edge tuples (u, v).