Graphs and Representations

1. What It Is and Why It Exists

A graph is a set of vertices (nodes) connected by edges. It exists because an enormous class of problems is fundamentally "things and relationships between them": road maps, social networks, course prerequisites, task dependencies, state machines. Trees and linked lists are just restricted graphs; the moment a problem has arbitrary connections, cycles, or "reachability/shortest path/dependency" language, it is a graph problem and you model it as one.

The representation you choose decides your complexity, so it's the first decision you state. An adjacency list maps each vertex to its neighbors — O(V + E) space, and you iterate a vertex's neighbors in O(degree). An adjacency matrix is a V×V grid where M[u][v] marks an edge — O(V^2) space but O(1) edge existence checks. The "why it works" intuition: real graphs are usually sparse (E ≪ V^2), so an adjacency list wastes no space and makes traversal O(V + E); you only prefer a matrix when the graph is dense or you need constant-time "is there an edge u→v?" checks. Most interview graphs are given as edge lists you convert to an adjacency list first.

2. Operations and Complexity

Most-probed facts: default to an adjacency list; BFS/DFS are O(V + E) on a list (each vertex and edge touched once); BFS on an unweighted graph gives the shortest path (fewest edges) because vertices leave the queue in non-decreasing distance order; a visited set is mandatory or cycles loop forever. Directed vs undirected and weighted vs unweighted change the build and the algorithm — clarify both before coding.

3. Implementation

Build an adjacency list from an edge list, then the two canonical traversals:

Copy
from collections import deque, defaultdict

def build_graph(n, edges, directed=False):       # edges: list of (u, v)
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        if not directed:                          # undirected => add both ways
            g[v].append(u)
    return g                                       # O(V + E) space

def bfs(g, start):                                # O(V + E); shortest path on UNWEIGHTED graph
    visited = {start}                              # mark on ENQUEUE, not on dequeue
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in g[node]:
            if nxt not in visited:                 # visited set => no infinite loop on cycles
                visited.add(nxt)
                q.append(nxt)
    return order

def _dfs_visit(g, node, visited, out):            # recursion stack O(V) worst case
    visited.add(node)
    out.append(node)
    for nxt in g[node]:
        if nxt not in visited:
            _dfs_visit(g, nxt, visited, out)

def dfs(g, start):                                # O(V + E)
    visited = set()
    out = []
    _dfs_visit(g, start, visited, out)
    return out

# Adjacency matrix (use only when dense or you need O(1) edge checks):
def build_matrix(n, edges):
    M = [[0] * n for _ in range(n)]                # O(V^2) space
    for u, v in edges:
        M[u][v] = M[v][u] = 1
    return M

In a real interview, don't define a graph class — use collections.defaultdict(list) for the adjacency list and collections.deque for the BFS queue; both are the expected idioms. A 2D grid problem is an implicit graph: cells are vertices, the 4 (or 8) neighbors are edges — no explicit graph build needed.

4. When to Reach for It

• Language signals: "network," "connections," "dependencies," "prerequisites," "reachable," "shortest path," "islands/regions," "cycle."
• Grid problems (number of islands, shortest path in a maze, rotting oranges) → treat the grid as an implicit graph, BFS/DFS over neighbor cells.
• Shortest path, fewest steps, minimum moves on an unweighted graph → BFS (it gives the minimum-edge path for free).
• Connectivity / components / cycle detection / topological order → DFS or BFS (or union-find for pure connectivity).
• Choose matrix only when the graph is dense or you need many O(1) "edge exists?" queries; otherwise adjacency list.

5. Common Pitfalls

• No visited set: traversing a graph with a cycle without marking visited loops forever — the single most common graph bug.
• Marking visited on dequeue instead of enqueue (BFS): the same node gets enqueued multiple times → blows up time/space and can break shortest-path correctness. Mark when you add to the queue.
• Forgetting undirected edges go both ways: adding only g[u].append(v) for an undirected graph silently loses half the connections.
• Using BFS for shortest path on a weighted graph: BFS only minimizes edge count; weighted graphs need Dijkstra (non-negative) or Bellman-Ford.
• Defaulting to an adjacency matrix: O(V^2) space TLEs/MLEs on large sparse graphs — list is the default.
• DFS recursion depth: O(V) stack on a long path can hit Python's recursion limit — mention an explicit stack for large inputs.
• Disconnected graph: one BFS/DFS from a single source misses other components — loop over all unvisited vertices when the whole graph matters.

6. Interview Cheat Sheet

• "I default to an adjacency list — O(V+E) space — and only use a matrix for dense graphs or O(1) edge-existence checks."
• "BFS and DFS are both O(V+E); BFS gives the shortest path on an unweighted graph because nodes dequeue in non-decreasing distance order."
• "A visited set is mandatory to handle cycles, and in BFS I mark visited on enqueue, not dequeue."
• "A 2D grid is an implicit graph: cells are vertices and the 4 neighbors are edges — no explicit build needed."

Follow-ups:

• "Adjacency list vs matrix?" — List: O(V+E) space, O(deg) neighbor iteration — best for sparse graphs. Matrix: O(V^2) space, O(1) edge check — only for dense graphs.
• "BFS vs DFS for shortest path?" — BFS gives the fewest-edges path on an unweighted graph. DFS does not (it finds a path, not the shortest). Weighted → Dijkstra/Bellman-Ford.
• "Detect a cycle?" — Undirected: DFS and find an already-visited node that isn't the parent (or union-find). Directed: DFS with a recursion/"in-progress" set — a back edge to a gray node is a cycle.