Data Structures & Algorithms Cheatsheet

Topological Sort

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

A topological order lists every vertex of a directed acyclic graph before all of its successors. It exists if and only if the graph has no cycle.

Task	Time	Space
Kahn's algorithm (BFS on in-degrees)	O(V + E)	O(V)
DFS postorder, reversed	O(V + E)	O(V) recursion
detect a cycle as a side effect	O(V + E)	O(V)
lexicographically smallest order	O(V log V + E)	O(V)
count all topological orders	O(2^V · V)	O(2^V)
longest path in a DAG	O(V + E)	O(V)
all-pairs reachability in a DAG	O(V · E)	O(V²)

Both algorithms are linear. Kahn's is preferred because it detects cycles without extra bookkeeping and generalizes to level-by-level scheduling.

When To Reach For This

Signals in a problem statement:

Prerequisites, dependencies, or ordering constraints. "Course A before course B", "task X requires Y", build systems, package installs.
The words "is it possible to finish", which is really "is this graph acyclic".
"Find any valid order" or "find the lexicographically smallest order".
A derived alphabet or ranking from pairwise comparisons, as in alien dictionaries.
A DAG where you need the longest path, which is NP-hard on general graphs but linear here.

Classic problems it solves:

Course Schedule and Course Schedule II
Alien Dictionary
Minimum Height Trees
Sequence Reconstruction
Parallel Courses (minimum semesters)
Sort Items by Groups Respecting Dependencies
Longest Increasing Path in a DAG

Kahn's Algorithm

Repeatedly take a vertex with in-degree 0. Removing it decrements its neighbors, which may expose new zero-in-degree vertices.

from collections import defaultdict, deque

def topo_kahn(n, edges):
    """edges: list of (u, v) meaning u must come before v.
    Returns an order, or [] if a cycle exists."""
    g = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == n else []      # short means a cycle

The length check is the cycle test. If the loop ends with fewer than n vertices, the leftovers all sit on or behind a cycle.

def course_schedule(num_courses, prerequisites):
    """prerequisites[i] = [course, prereq]. True if all can be finished."""
    g = defaultdict(list)
    indeg = [0] * num_courses
    for course, prereq in prerequisites:
        g[prereq].append(course)                 # prereq -> course
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == num_courses

def topo_smallest(n, edges):
    """Lexicographically smallest valid order. Heap instead of a queue."""
    import heapq
    g = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1
    pq = [u for u in range(n) if indeg[u] == 0]
    heapq.heapify(pq)
    order = []
    while pq:
        u = heapq.heappop(pq)
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(pq, v)
    return order if len(order) == n else []

// Java: Kahn's with an int[] in-degree array and an ArrayDeque
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }

Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
    int u = q.poll();
    order[k++] = u;
    for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
}
if (k != n) return new int[0];        // cycle

DFS Postorder

A vertex is appended only after every descendant is finished, so the reversed postorder is a valid topological order.

def topo_dfs(n, edges):
    """Returns an order, or [] on a cycle. Three-color DFS."""
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []

    def dfs(u):
        color[u] = GRAY
        for v in g[u]:
            if color[v] == GRAY:
                return False           # back edge, cycle
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        order.append(u)                # postorder append
        return True

    for u in range(n):
        if color[u] == WHITE and not dfs(u):
            return []
    return order[::-1]                 # reverse the postorder

def topo_dfs_iterative(n, g):
    """No recursion limit. Push (vertex, child index) frames."""
    color = [0] * n
    order = []
    for s in range(n):
        if color[s]:
            continue
        st = [(s, 0)]
        color[s] = 1
        while st:
            u, i = st.pop()
            if i < len(g[u]):
                st.append((u, i + 1))
                v = g[u][i]
                if color[v] == 1:
                    return []          # cycle
                if color[v] == 0:
                    color[v] = 1
                    st.append((v, 0))
            else:
                color[u] = 2
                order.append(u)
    return order[::-1]

GRAY means "on the current path". A single boolean visited set cannot detect directed cycles, it reports false positives on any diamond shape.

Level-By-Level Scheduling

Freezing the queue length per round groups vertices that can run in parallel, which answers "minimum number of semesters" or "minimum build rounds".

def min_semesters(n, relations):
    """Fewest terms to finish all courses, unlimited courses per term."""
    g = defaultdict(list)
    indeg = [0] * (n + 1)
    for prev, nxt in relations:
        g[prev].append(nxt)
        indeg[nxt] += 1
    q = deque(c for c in range(1, n + 1) if indeg[c] == 0)
    terms, done = 0, 0
    while q:
        terms += 1
        for _ in range(len(q)):        # one whole term per round
            u = q.popleft()
            done += 1
            for v in g[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
    return terms if done == n else -1

def min_height_trees(n, edges):
    """Peel leaves inward. The last 1 or 2 vertices are the centroids.
    Undirected, so the in-degree here is the plain degree."""
    if n == 1:
        return [0]
    g = defaultdict(set)
    for u, v in edges:
        g[u].add(v)
        g[v].add(u)
    leaves = [u for u in range(n) if len(g[u]) == 1]
    remaining = n
    while remaining > 2:
        remaining -= len(leaves)
        nxt = []
        for leaf in leaves:
            nb = g[leaf].pop()
            g[nb].discard(leaf)
            if len(g[nb]) == 1:
                nxt.append(nb)
        leaves = nxt
    return leaves

Downstream Uses

def longest_path_dag(n, edges):
    """Longest path in edges. Linear on a DAG, NP-hard in general."""
    order = topo_kahn(n, edges)
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
    dp = [0] * n
    for u in order:
        for v in g[u]:
            dp[v] = max(dp[v], dp[u] + 1)
    return max(dp, default=0)

def alien_order(words):
    """Derive the alphabet order from a sorted dictionary."""
    g = defaultdict(set)
    indeg = {ch: 0 for w in words for ch in w}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                if y not in g[x]:
                    g[x].add(y)
                    indeg[y] += 1
                break
        else:
            if len(a) > len(b):
                return ""              # "abc" before "ab" is invalid input
    q = deque(c for c in indeg if indeg[c] == 0)
    out = []
    while q:
        c = q.popleft()
        out.append(c)
        for nxt in g[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return "".join(out) if len(out) == len(indeg) else ""

Any DP over a DAG runs in topological order, which is exactly what makes DAG DP linear. That includes DAG shortest and longest paths, path counting, and reachability.

Gotchas

Edge direction. "A requires B" means the edge points B → A, since B must come first. Reversing it produces a valid-looking order that is wrong.
The cycle check is the length check. len(order) == n after Kahn's, or the GRAY test in DFS. Skipping it returns a truncated order silently.
A single visited set does not detect directed cycles. You need three colors, or in-degree counting.
Isolated vertices belong in the order. Seed the queue from every vertex with in-degree 0, including those with no edges at all.
Duplicate edges inflate in-degree. Deduplicate with a set of edges first, or the count never reaches 0.
1-indexed vertices. Size arrays n + 1 and seed the queue from range(1, n + 1).
Topological order is not unique. Any valid order passes unless the problem asks for the lexicographically smallest, which needs a heap.
Undirected graphs have no topological order. Every edge would be a two-way constraint. Leaf-peeling is the undirected analogue.
Recursion depth on a 10⁵-vertex chain overflows Python's stack. Use Kahn's or the iterative DFS.