What is Topological Sort?
A topological ordering of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge u→v, vertex u comes before v. Only valid for DAGs — cycles have no valid topological order. Used for: course prerequisite ordering, build system dependency resolution, task scheduling.
Kahn’s Algorithm (BFS-based)
Compute in-degree for all nodes. Process nodes with in-degree 0 (no prerequisites). When a node is processed, decrement in-degree of its neighbors. Add newly zero-in-degree neighbors to the queue. If the output length equals the number of nodes: valid topological order (no cycle). If less: cycle detected.
from collections import deque
def topological_sort(n, prerequisites):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in prerequisites: # v must come before u
graph[v].append(u)
indegree[u] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else [] # empty = cycle
LC 207 (Course Schedule — detect cycle), LC 210 (Course Schedule II — return order), LC 269 (Alien Dictionary — build graph from adjacent word pairs).
DFS-Based Topological Sort
Post-order DFS: after visiting all descendants, add the current node to the result. Reverse at end. 3-color marking detects cycles (WHITE=unvisited, GRAY=in-stack, BLACK=done).
def topo_dfs(n, graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
order = []
has_cycle = [False]
def dfs(u):
if has_cycle[0]: return
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY:
has_cycle[0] = True; return
if color[v] == WHITE:
dfs(v)
color[u] = BLACK
order.append(u)
for i in range(n):
if color[i] == WHITE:
dfs(i)
return [] if has_cycle[0] else order[::-1]
Alien Dictionary (LC 269)
Build the character dependency graph from adjacent words in the sorted alien list. For each pair of adjacent words: find the first differing character; that gives an edge (earlier_char → later_char). If word A is a prefix of shorter word B and A comes after B: invalid. Then run topological sort on the character graph. Return empty string if cycle detected.
def alienOrder(words):
graph = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return "" # invalid
for j in range(min_len):
if w1[j] != w2[j]:
graph[w1[j]].add(w2[j])
break
# run Kahn's on graph
...
Parallel Course Scheduling (LC 1136)
Find the minimum number of semesters to complete all courses, where you can take any number of courses per semester as long as prerequisites are satisfied. Answer = the length of the longest path in the DAG. Compute using topological order: for each node, semester[u] = max(semester[v] for v in prerequisites[u]) + 1.
Key Patterns
- Kahn’s preferred in interviews — BFS is intuitive and naturally detects cycles (count check)
- DFS topological sort: useful when you need to detect specific cycle nodes (not just existence)
- Build system / task scheduler: nodes=tasks, edges=dependencies, topological sort gives valid execution order
- Longest path in DAG: use topological order + DP (no negative-weight shortest path needed)
- If the graph might have cycles: Kahn’s count check (or 3-color DFS) detects them; regular DFS visited-set does NOT detect cycles in directed graphs
Meta coding interviews test topological sort and graph dependency patterns. See common questions for Meta interview: topological sort and dependency problems.
Google coding interviews frequently test topological sort patterns. See problems for Google interview: topological sort and course schedule problems.
Atlassian coding rounds include topological sort and build system problems. See patterns for Atlassian interview: topological sort and task dependency problems.