Graphs Overview

A Graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E$ connecting them. Trees are a special case of graphs — connected, acyclic, and undirected.

Graph Types

Type	Description
Undirected	Edges have no direction: `u — v` means `u → v` and `v → u`
Directed (Digraph)	Edges have direction: `u → v` does not imply `v → u`
Weighted	Each edge carries a numeric weight (cost, distance)
Unweighted	All edges have equal weight (or weight 1)
Cyclic	Contains at least one cycle
Acyclic (DAG)	Directed Acyclic Graph — no cycles

Representations

Adjacency List (most common)

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
}

Space: $O(V + E)$ . Fast iteration over neighbors.

Adjacency Matrix

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0],
]

Space: $O(V^2)$ . $O(1)$ edge lookup, but wasteful for sparse graphs.

Edge List

edges = [(0, 1), (0, 2), (1, 3)]

Simple, but $O(E)$ to find neighbors.

Building a Graph from Edge Input

from collections import defaultdict

def build_graph(n: int, edges: list[list[int]]) -> dict:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)   # omit this line for directed graphs
    return graph

Topological Sort (Directed Acyclic Graphs)

A topological order lists nodes so that every edge u → v has u before v. Used for scheduling problems (course prerequisites).

from collections import deque

def topo_sort(n: int, prerequisites: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    in_degree = [0] * n

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []   # empty if cycle detected

Practice Problems

Done	Question	Difficulty
	Course Schedule	Medium
	Course Schedule II	Medium