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
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is topological sort and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge u→v, u appears before v. It is only valid for DAGs — cyclic graphs have no valid topological order. Use topological sort when: you need to process nodes in dependency order (build systems: compile module A before B if A depends on B), course prerequisite scheduling (LC 207/210), detecting circular dependencies, and finding the critical path in project scheduling. If the graph has a cycle, topological sort should report an error (cycle = impossible scheduling). Interview signal: any problem with "prerequisites" or "dependencies" is a topological sort problem.”}},{“@type”:”Question”,”name”:”What is the difference between Kahn's algorithm and DFS-based topological sort?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Kahn's algorithm (BFS): compute in-degrees, process nodes with in-degree 0, decrement neighbors. Naturally detects cycles by checking if processed count equals total nodes. Easy to implement, intuitive. Returns the topological order directly. DFS-based: post-order DFS — add node to result after all descendants are processed, then reverse. Requires 3-color marking (WHITE/GRAY/BLACK) to detect cycles in directed graphs. Returns reverse post-order. Choose Kahn's in interviews: it's more readable, the cycle detection is a simple count check, and it naturally processes nodes level by level (useful for LC 1136 where you need to count the number of levels). Use DFS-based when you need to find the actual cycle path (not just detect its existence).”}},{“@type”:”Question”,”name”:”How do you build the graph for Alien Dictionary (LC 269)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The alien dictionary problem gives you words sorted in the alien language's alphabetical order. To find the character ordering: for each pair of adjacent words, find the first position where they differ — that gives you one edge (word1[i] comes before word2[i] in the alien alphabet). Handle the edge case: if word1 is longer than word2 and word1 starts with word2 (e.g., ["abc", "ab"]), return empty string (invalid ordering). After building the edge set for all character pairs, run topological sort. If a cycle is detected: return empty string (contradictory ordering). The output is the topological order of characters. Time O(sum of word lengths) for graph building + O(V+E) for topological sort.”}},{“@type”:”Question”,”name”:”How do you find the minimum number of semesters to complete all courses?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 1136 (Parallel Courses) or LC 630 (Course Schedule III variant). The minimum semesters equals the length of the longest path in the DAG. Compute using topological order: semester[u] = 1 + max(semester[v] for all v that must come before u). Process in topological order (Kahn's BFS level by level): all nodes processed in the same BFS level (same in-degree wave) can be taken in the same semester. The answer is the number of BFS levels. In Kahn's: instead of a single queue, process level by level. Each level = one semester. Courses with no prerequisites are level 1. Courses whose prerequisites are all in level k are in level k+1.”}},{“@type”:”Question”,”name”:”How do you detect a cycle in a directed graph?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”DFS 3-color algorithm: WHITE (unvisited), GRAY (in current recursion stack), BLACK (fully processed). For each unvisited node, run DFS. Mark the node GRAY on entry, BLACK on exit. If DFS encounters a GRAY node: cycle detected (back edge in the recursion stack). A BLACK node is not a cycle — it was fully processed via a different path. Do NOT use a simple visited set for directed graphs: a node can be reachable via two paths without a cycle, and marking it as visited the first time would incorrectly skip the second path. Kahn's cycle detection: if the total processed count < total nodes after Kahn's completes, the unprocessed nodes form cycles. LC 207, 802 (Find Eventual Safe States).”}}]}
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.