Representing graphs

A graph is a set of vertices (nodes) connected by edges. Edges can be undirected (a friendship goes both ways) or directed (a follow goes one way), and weighted (a road has a length) or unweighted. A tree is a special graph: connected, with no cycles, and exactly V - 1 edges.

An adjacency list stores, for each vertex, the list of its neighbours. It uses O(V + E) memory and lists a vertex's neighbours in O(degree) time. An adjacency matrix is a V by V grid where cell [u][v] is 1 (or the weight) if an edge exists. It uses O(V^2) memory but checks any edge in O(1).

An edge list is just a list of (u, v, weight) tuples, which is how most interview inputs arrive and what Kruskal's algorithm wants. A grid is an implicit graph: each cell is a node and its up, down, left and right neighbours are edges, computed on the fly instead of stored.

1. 1Identify the vertices (people, cells, words, states) and what makes an edge between them.
2. 2Decide directed or undirected and weighted or not. Undirected edges are stored twice, once from each end.
3. 3Choose a structure: adjacency list for most sparse graphs (E much smaller than V^2), matrix for small dense graphs or when you need O(1) edge checks.
4. 4Build it in one pass over the edge list: for each (u, v), append v to adj[u] (and u to adj[v] if undirected). For weights, append (v, w).
5. 5For grids, do not build anything: generate neighbours with direction offsets and a bounds check while traversing.

from collections import defaultdict

def build_adj(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)          # undirected: store both ways
    return adj

def build_weighted(edges):
    adj = defaultdict(list)            # works for non-integer node names
    for u, v, w in edges:
        adj[u].append((v, w))
    return adj

def build_matrix(n, edges):
    m = [[0] * n for _ in range(n)]
    for u, v in edges:
        m[u][v] = m[v][u] = 1
    return m

def grid_neighbors(grid, r, c):
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            yield nr, nc

build_adj is the line you will write in nearly every graph problem. build_weighted stores (neighbour, weight) pairs for Dijkstra. build_matrix shows the O(V^2) alternative. grid_neighbors generates edges of an implicit grid graph on demand.

Cost: Adjacency list: O(V + E) space, O(deg) to list or check neighbours. Matrix: O(V^2) space, O(1) edge check, O(V) to list neighbours. Edge list: O(E) space.