LeetCode Patterns ·

🎯 Topological Sort

1️⃣ Core Framework

When discussing Topological Sort, I frame it as:

What problem pattern it solves
Directed acyclic graph
Dependency ordering
Indegree and Kahn’s algorithm
DFS-based topological sort
Cycle detection
Course Schedule
Alien Dictionary
Common edge cases
Senior-level explanation

2️⃣ What Problem Are We Solving?

Topological sort is used when we need to order tasks with dependencies.

It is commonly used for:

Course prerequisites
Build systems
Task scheduling
Package dependency resolution
Workflow execution
Alien dictionary ordering
Detecting impossible dependency cycles
Ordering nodes in a DAG

The core idea is:

If A must happen before B,
then A should appear before B in the ordering.

👉 Interview Answer

Topological sort is an ordering of nodes in a directed graph such that every dependency appears before the node that depends on it.

It only exists for directed acyclic graphs.

If the graph has a cycle, no valid topological ordering exists.

3️⃣ Directed Acyclic Graph

DAG

Topological sort applies to a:

Directed Acyclic Graph

That means:

Directed: edges have direction
Acyclic: no cycles

Example

A → B
A → C
B → D
C → D

Valid topological orders:

A, B, C, D
A, C, B, D

Invalid order:

B, A, C, D

Because:

A must come before B

👉 Interview Answer

Topological sort only works on a directed acyclic graph.

The directed edges represent dependencies.

If there is an edge from A to B, then A must appear before B in the ordering.

If a cycle exists, the dependencies are impossible to satisfy.

4️⃣ Why Topological Sort Works

Dependency View

If a node has no prerequisites:

indegree = 0

Then it can be processed immediately.

After processing it, we remove its outgoing edges.

This may unlock other nodes.

Example

A → B
A → C
B → D
C → D

Initial indegree:

A: 0
B: 1
C: 1
D: 2

Process A:

B indegree becomes 0
C indegree becomes 0

Process B and C:

D indegree becomes 0

👉 Interview Answer

Topological sort works by repeatedly processing nodes that have no remaining prerequisites.

Once a node is processed, we remove its outgoing edges and reduce the indegree of its neighbors.

If all nodes can be processed, the graph is acyclic.

If some nodes remain blocked, the graph contains a cycle.

5️⃣ Kahn’s Algorithm

Core Idea

Kahn’s algorithm uses indegree.

indegree[node] = number of prerequisites remaining

Steps:

Build graph and indegree array.
Add all nodes with indegree 0 to queue.
Pop from queue and add to order.
Reduce indegree of neighbors.
If neighbor indegree becomes 0, add it to queue.
If order size == number of nodes, success.

Template

from collections import deque

def topological_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != n:
        return []

    return order

👉 Interview Answer

Kahn’s algorithm performs topological sort using indegree.

Nodes with indegree zero have no remaining prerequisites, so they can be processed.

After processing a node, I reduce the indegree of its neighbors.

If a neighbor’s indegree becomes zero, it is ready to process.

If we cannot process all nodes, the graph has a cycle.

6️⃣ Building the Graph

Edge Direction Matters

If the input means:

[a, b] means b must be taken before a

Then edge should be:

b → a

Because:

b is prerequisite of a

Course Schedule Example

Input:

[course, prerequisite]

So:

graph[prerequisite].append(course)
indegree[course] += 1

Common Mistake

Wrong direction:

graph[course].append(prerequisite)

This reverses the dependency order.

👉 Interview Answer

The most important implementation detail is edge direction.

If b is a prerequisite of a, the graph edge should be b to a.

That means after completing b, we unlock a.

Getting edge direction wrong is one of the most common topological sort bugs.

7️⃣ Course Schedule I

Problem

Given courses and prerequisites, determine whether all courses can be finished.

Key Insight

This is cycle detection in a directed graph.

If there is a cycle,
courses depend on each other,
so completion is impossible.

Code With Kahn’s Algorithm

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    return completed == num_courses

👉 Interview Answer

Course Schedule is a directed graph cycle detection problem.

I build edges from prerequisite to course.

Then I use indegree-based topological sorting.

If I can process all courses, there is no cycle.

If some courses remain unprocessed, the graph contains a cycle and not all courses can be finished.

8️⃣ Course Schedule II

Problem

Return one valid order to take all courses.

If impossible, return empty list.

Code

from collections import deque

def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    order = []

    while queue:
        course = queue.popleft()
        order.append(course)

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    if len(order) != num_courses:
        return []

    return order

Key Difference

Course Schedule I asks:

Can we finish?

Course Schedule II asks:

What is one valid order?

👉 Interview Answer

Course Schedule II is the same topological sort pattern, but instead of only counting processed courses, I store the actual order.

If the final order contains all courses, it is a valid topological order.

Otherwise, a cycle exists and I return an empty list.

9️⃣ DFS-Based Topological Sort

Core Idea

DFS can also produce topological order.

For each node:

visit all descendants first
then add current node to result

This is postorder.

Finally reverse the result.

Node States

Use three states:

= unvisited
= visiting
= visited

If DFS reaches a visiting node:

cycle detected

Code

def topo_sort_dfs(n, edges):
    graph = [[] for _ in range(n)]

    for a, b in edges:
        graph[a].append(b)

    state = [0] * n
    order = []

    def dfs(node):
        if state[node] == 1:
            return False

        if state[node] == 2:
            return True

        state[node] = 1

        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False

        state[node] = 2
        order.append(node)
        return True

    for node in range(n):
        if state[node] == 0:
            if not dfs(node):
                return []

    order.reverse()
    return order

👉 Interview Answer

DFS-based topological sort uses postorder traversal.

I first visit all neighbors of a node, then add the node to the ordering.

Finally, I reverse the postorder result.

I use three states to detect cycles: unvisited, visiting, and visited.

If DFS reaches a visiting node, there is a cycle.

🔟 Kahn vs DFS Topological Sort

Kahn’s Algorithm

Uses:

indegree + queue

Good for:

finding valid order
detecting cycles by processed count
level-style dependency processing

DFS Topological Sort

Uses:

recursion + postorder

Good for:

cycle detection
dependency recursion
postorder reasoning

Comparison

Approach	Data Structure	Cycle Detection	Output
Kahn	Queue + indegree	processed count < n	direct order
DFS	Recursion + states	visiting node found	reverse postorder

👉 Interview Answer

Kahn’s algorithm uses indegree and queue.

DFS topological sort uses recursion and postorder.

Both are O(V + E).

I usually prefer Kahn’s algorithm when I need a straightforward dependency order, and DFS when the problem is naturally recursive or cycle detection is the main focus.

1️⃣1️⃣ Cycle Detection

Why Cycle Breaks Topological Sort

Example:

A → B
B → C
C → A

This means:

A before B
B before C
C before A

Impossible.

Kahn’s Cycle Detection

If queue becomes empty before all nodes are processed:

cycle exists

Because remaining nodes still have indegree > 0.

DFS Cycle Detection

If DFS reaches a node currently in recursion stack:

cycle exists

That node has state:

visiting

👉 Interview Answer

A topological order cannot exist if the directed graph has a cycle.

With Kahn’s algorithm, a cycle is detected if we cannot process all nodes.

With DFS, a cycle is detected when we reach a node that is currently in the recursion stack.

1️⃣2️⃣ Alien Dictionary

Problem

Given words sorted according to an unknown alphabet, derive the order of characters.

Example:

["wrt", "wrf", "er", "ett", "rftt"]

One valid output:

"wertf"

Key Insight

Compare adjacent words.

Find the first different character.

wrt
wrf

First difference:

t before f

So edge:

t → f

Invalid Prefix Case

["abc", "ab"]

This is invalid because a longer word appears before its prefix.

Code

from collections import deque

def alien_order(words):
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]

        if len(word1) > len(word2) and word1.startswith(word2):
            return ""

        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    indegree[c2] += 1
                break

    queue = deque([char for char in indegree if indegree[char] == 0])
    order = []

    while queue:
        char = queue.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(indegree):
        return ""

    return "".join(order)

👉 Interview Answer

Alien Dictionary can be modeled as topological sort.

Each character is a node.

By comparing adjacent words, we infer ordering constraints between characters.

The first different character gives a directed edge.

Then we run topological sort.

If there is a cycle or invalid prefix case, no valid order exists.

1️⃣3️⃣ Minimum Height Trees

Problem

Given an undirected tree, find all roots that produce minimum height.

Why Topological-Like BFS?

This problem is not classic directed topological sort, but it uses a similar trimming idea.

Leaves have degree 1.

Repeatedly remove leaves.

The remaining center nodes are the answer.

Code

from collections import deque

def find_min_height_trees(n, edges):
    if n == 1:
        return [0]

    graph = [set() for _ in range(n)]

    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)

    leaves = deque()

    for node in range(n):
        if len(graph[node]) == 1:
            leaves.append(node)

    remaining = n

    while remaining > 2:
        size = len(leaves)
        remaining -= size

        for _ in range(size):
            leaf = leaves.popleft()
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)

            if len(graph[neighbor]) == 1:
                leaves.append(neighbor)

    return list(leaves)

👉 Interview Answer

Minimum Height Trees is not standard topological sort because the graph is undirected.

But it uses a similar degree-based trimming idea.

We repeatedly remove leaves from the outside.

The last one or two remaining nodes are the tree centers, which produce minimum height.

1️⃣4️⃣ Task Scheduling

Problem Pattern

Given tasks and dependencies, return a valid execution order.

Example:

A before C
B before C
C before D

Valid order:

A, B, C, D

or:

B, A, C, D

Topological Sort Model

Task = node
Dependency = directed edge
No dependency = indegree 0

Key Insight

Tasks with no prerequisites can start first.

After finishing a task, its dependent tasks may become available.

👉 Interview Answer

Task scheduling is a natural topological sort problem.

Each task is a node.

Each dependency is a directed edge from prerequisite to dependent task.

Tasks with indegree zero are ready to run.

Processing a task reduces the indegree of its dependents.

1️⃣5️⃣ Build System Dependency Order

Example

Suppose:

parser must build before compiler
compiler must build before optimizer
optimizer must build before runtime

Edges:

parser → compiler
compiler → optimizer
optimizer → runtime

Valid build order:

parser, compiler, optimizer, runtime

If There Is a Cycle

compiler → optimizer
optimizer → compiler

This means:

compiler needs optimizer
optimizer needs compiler

No valid build order exists.

👉 Interview Answer

Build systems often use dependency graphs.

Each module is a node, and each dependency is a directed edge.

Topological sort produces a valid build order.

If the graph has a cycle, the build dependencies are invalid.

1️⃣6️⃣ Topological Sort With Multiple Valid Answers

Important Note

Topological order is not always unique.

Example:

A → C
B → C

Valid orders:

A, B, C
B, A, C

Why?

Both A and B have indegree 0 initially.

Either can be processed first.

Interview Implication

If problem asks:

return any valid order

Any topological order is fine.

If problem asks:

lexicographically smallest order

Use a min-heap instead of a queue.

👉 Interview Answer

A graph can have multiple valid topological orders.

If multiple nodes have indegree zero, any of them can be processed next.

If the problem requires the lexicographically smallest order, I would use a min-heap instead of a queue.

1️⃣7️⃣ Lexicographically Smallest Topological Order

Problem

Return the smallest topological order by node value or character.

Key Change

Use a min-heap instead of queue:

import heapq

This always processes the smallest available node first.

Code

import heapq

def topo_sort_lexicographically_smallest(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1

    heap = []

    for node in range(n):
        if indegree[node] == 0:
            heapq.heappush(heap, node)

    order = []

    while heap:
        node = heapq.heappop(heap)
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                heapq.heappush(heap, neighbor)

    if len(order) != n:
        return []

    return order

👉 Interview Answer

If multiple topological orders exist and the problem asks for the smallest order, I replace the queue with a min-heap.

The heap always picks the smallest currently available node with indegree zero.

The rest of the algorithm is the same as Kahn’s algorithm.

1️⃣8️⃣ Topological Sort vs BFS

Relationship

Kahn’s algorithm looks like BFS.

It uses:

queue
level-style processing
neighbor expansion

But the meaning is different.

BFS

Queue contains:

nodes by distance from source

Kahn’s Algorithm

Queue contains:

nodes with no remaining prerequisites

👉 Interview Answer

Kahn’s algorithm looks like BFS because it uses a queue.

But BFS is organized by distance from a source.

Topological sort is organized by dependency readiness.

A node enters the queue when its indegree becomes zero, not because it is one edge farther from a source.

1️⃣9️⃣ Topological Sort vs DFS

DFS Traversal

DFS explores deeply:

node → neighbor → neighbor's neighbor

DFS Topological Sort

DFS topological sort uses postorder:

process descendants first
then add current node

Key Difference

Regular DFS gives traversal order.

DFS topological sort gives dependency order after reversing postorder.

👉 Interview Answer

DFS traversal order is not automatically a topological order.

For DFS-based topological sort, I add a node only after all of its descendants are processed.

This postorder result is then reversed to produce a topological order.

2️⃣0️⃣ Complexity Analysis

Time Complexity

For graph with V vertices and E edges:

O(V + E)

Because:

build graph: O(E)
process each node once: O(V)
process each edge once: O(E)

Space Complexity

O(V + E)

For:

graph adjacency list
indegree array
queue or recursion stack
result order

Heap Version

If using min-heap:

O((V + E) log V)

Because heap operations cost:

O(log V)

👉 Interview Answer

Topological sort is O(V + E) time and O(V + E) space.

Each node is processed once, and each edge is examined once.

If we use a heap to get lexicographically smallest order, the complexity becomes O((V + E) log V).

2️⃣1️⃣ Common Edge Cases

No Edges

n = 3
edges = []

Any order is valid:

[0, 1, 2]

Single Node

n = 1

Order:

[0]

Cycle

0 → 1
1 → 0

No valid order.

Return:

[]
False
""

depending on the problem.

Disconnected DAG

0 → 1
2 → 3

Need process all components.

Duplicate Edges

Duplicate edges may incorrectly increase indegree multiple times.

Need handle if input may contain duplicates.

Invalid Prefix in Alien Dictionary

["abc", "ab"]

Invalid.

👉 Interview Answer

Common edge cases include no edges, single node, cycles, disconnected DAGs, duplicate edges, and invalid prefix cases in Alien Dictionary.

I make sure to initialize every node, not just nodes that appear in edges.

2️⃣2️⃣ Common Mistakes

Mistake 1: Wrong Edge Direction

For prerequisites:

prerequisite → course

not:

course → prerequisite

Mistake 2: Forgetting Nodes With No Edges

All nodes must be initialized.

A course with no prerequisites should still appear in the result.

Mistake 3: Not Detecting Cycles

Need check:

len(order) == n

or use DFS states.

Mistake 4: Duplicate Edge Bugs

If duplicate edges exist:

a → b
a → b

indegree may be incremented twice incorrectly.

Use set if needed.

Mistake 5: Confusing BFS Shortest Path With Topological Sort

Both may use queue, but queue meaning is different.

👉 Interview Answer

Common topological sort mistakes include wrong edge direction, forgetting isolated nodes, not checking for cycles, mishandling duplicate edges, and confusing Kahn’s queue with BFS distance queue.

I always define what an edge means before building the graph.

2️⃣3️⃣ When Topological Sort Applies

Good Fit

Use topological sort when the problem asks for:

dependency ordering
prerequisite scheduling
build order
task execution order
valid ordering with constraints
detecting impossible dependency cycles
DAG ordering

Problem Signals

Look for words like:

prerequisite
dependency
before
after
course schedule
build order
tasks
workflow
must happen before
alien dictionary

👉 Interview Answer

I consider topological sort when the problem involves directed dependencies.

If some tasks must happen before others, or if we need to detect impossible dependency cycles, topological sort is usually the right pattern.

2️⃣4️⃣ When Topological Sort Does Not Apply

Not Good Fit

Topological sort is not suitable when:

graph is undirected
dependencies can contain valid cycles
need shortest path
need minimum cost
need all possible orders
need dynamic updates frequently

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Undirected components	DFS / BFS / Union Find
Need all valid orders	Backtracking + topological constraints
Dynamic dependency updates	Specialized graph data structure
Minimum spanning tree	Kruskal / Prim

👉 Interview Answer

Topological sort applies to directed acyclic dependency graphs.

If the graph is undirected, or if the problem asks for shortest path or minimum cost, topological sort is usually not the right tool.

If all valid orders are required, we may need backtracking on top of topological constraints.

2️⃣5️⃣ Standard Templates

Kahn’s Algorithm Template

from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for pre, nxt in edges:
        graph[pre].append(nxt)
        indegree[nxt] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != n:
        return []

    return order

Course Schedule Template

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    return completed == num_courses

DFS Topological Sort Template

def topo_sort_dfs(n, edges):
    graph = [[] for _ in range(n)]

    for pre, nxt in edges:
        graph[pre].append(nxt)

    state = [0] * n
    order = []

    def dfs(node):
        if state[node] == 1:
            return False

        if state[node] == 2:
            return True

        state[node] = 1

        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False

        state[node] = 2
        order.append(node)
        return True

    for node in range(n):
        if state[node] == 0:
            if not dfs(node):
                return []

    order.reverse()
    return order

Alien Dictionary Template

from collections import deque

def alien_order(words):
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]

        if len(word1) > len(word2) and word1.startswith(word2):
            return ""

        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    indegree[c2] += 1
                break

    queue = deque([char for char in indegree if indegree[char] == 0])
    order = []

    while queue:
        char = queue.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(indegree):
        return ""

    return "".join(order)

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Topological sort is used to order nodes in a directed graph with dependencies.

If there is an edge from A to B, then A must appear before B in the ordering.

This only works for directed acyclic graphs. If the graph has a cycle, no valid topological order exists.

The most common implementation is Kahn’s algorithm. It uses an indegree array and a queue.

Indegree represents how many prerequisites a node still has. Nodes with indegree zero have no remaining prerequisites, so they are ready to process.

After processing a node, we reduce the indegree of its neighbors. If a neighbor’s indegree becomes zero, it is added to the queue.

If we process all nodes, we have a valid topological order. If we cannot process all nodes, there must be a cycle.

Another approach is DFS-based topological sort. DFS visits all descendants first, then adds the current node to a postorder list. Reversing that postorder gives a topological order.

DFS also detects cycles using three states: unvisited, visiting, and visited. If DFS reaches a visiting node, the graph has a cycle.

Course Schedule is a classic topological sort problem. Courses are nodes, prerequisites are directed edges, and a cycle means the courses cannot all be completed.

Alien Dictionary is another example. Characters are nodes. Ordering constraints come from comparing adjacent words and finding the first different character. Then topological sort produces one valid character order.

A key implementation detail is edge direction. If b is a prerequisite of a, the edge should be b to a, not a to b.

Topological order may not be unique. If multiple nodes have indegree zero, any of them can appear next. If the lexicographically smallest order is required, I would use a min-heap instead of a queue.

The complexity is O(V + E), because each node and edge is processed once.

At a senior level, I would explain: what the nodes represent, what the directed edges mean, how indegree represents remaining dependencies, how cycles are detected, and why topological sort is only valid for DAGs.

⭐ Final Insight

Topological Sort 的核心不是“用 queue 排序”。

它的核心是 dependency readiness。

Senior-level 的重点是：

node 是什么， edge 方向代表什么， indegree 表示什么，哪些 node 可以先处理，如何判断 cycle，以及为什么只有 DAG 才有 valid ordering。

能讲清楚这些， Topological Sort 就是一种解决 dependency ordering 和 cycle detection 的核心图算法模式。

中文部分

🎯 Topological Sort

1️⃣ 核心框架

讨论 Topological Sort 时，我通常从：

它解决什么问题
Directed acyclic graph
Dependency ordering
Indegree 和 Kahn’s algorithm
DFS-based topological sort
Cycle detection
Course Schedule
Alien Dictionary
常见 edge cases
高级工程师解释方式

2️⃣ 要解决什么问题？

Topological sort 用于处理有依赖关系的任务排序。

它常用于：

Course prerequisites
Build systems
Task scheduling
Package dependency resolution
Workflow execution
Alien dictionary ordering
Detecting impossible dependency cycles
Ordering nodes in a DAG

核心思想是：

如果 A 必须在 B 之前发生，
那么 A 在排序中必须出现在 B 前面。

👉 面试回答

Topological sort 是 directed graph 中的一种 ordering。

它保证每个 dependency 都出现在依赖它的 node 之前。

Topological sort 只存在于 directed acyclic graph 中。

如果 graph 有 cycle，就不存在 valid topological ordering。

3️⃣ Directed Acyclic Graph

DAG

Topological sort 适用于：

Directed Acyclic Graph

也就是：

Directed: edge 有方向
Acyclic: 没有 cycle

Example

A → B
A → C
B → D
C → D

Valid topological orders:

A, B, C, D
A, C, B, D

Invalid order:

B, A, C, D

因为：

A must come before B

👉 面试回答

Topological sort 只适用于 directed acyclic graph。

Directed edges 表示 dependency。

如果有 edge A → B，说明 A 必须在 B 前面。

如果存在 cycle，这些 dependency 无法同时满足。

4️⃣ 为什么 Topological Sort 有效？

Dependency View

如果一个 node 没有 prerequisites：

indegree = 0

那么它可以立刻被处理。

处理完它之后，移除它的 outgoing edges。

这可能会解锁其他 nodes。

Example

A → B
A → C
B → D
C → D

Initial indegree:

A: 0
B: 1
C: 1
D: 2

处理 A：

B indegree becomes 0
C indegree becomes 0

处理 B 和 C：

D indegree becomes 0

👉 面试回答

Topological sort 的核心是不断处理没有剩余 prerequisites 的 nodes。

当一个 node 被处理后，它的 outgoing edges 被移除， neighbors 的 indegree 会减少。

如果所有 nodes 都能被处理，说明 graph 没有 cycle。

如果有些 nodes 一直无法处理，说明 graph 中存在 cycle。

5️⃣ Kahn’s Algorithm

Core Idea

Kahn’s algorithm 使用 indegree。

indegree[node] = 剩余 prerequisite 数量

Steps:

Build graph and indegree array.
Add all nodes with indegree 0 to queue.
Pop from queue and add to order.
Reduce indegree of neighbors.
If neighbor indegree becomes 0, add it to queue.
If order size == number of nodes, success.

Template

from collections import deque

def topological_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != n:
        return []

    return order

👉 面试回答

Kahn’s algorithm 使用 indegree 和 queue 做 topological sort。

Indegree 为 0 的 node 没有剩余 prerequisite，所以可以先处理。

处理一个 node 后，我会减少它 neighbors 的 indegree。

如果某个 neighbor 的 indegree 变成 0，就把它加入 queue。

如果最后不能处理所有 nodes，说明 graph 有 cycle。

6️⃣ 构建 Graph

Edge Direction 很重要

如果输入表示：

[a, b] means b must be taken before a

那么 edge 应该是：

b → a

因为：

b is prerequisite of a

Course Schedule Example

Input:

[course, prerequisite]

所以：

graph[prerequisite].append(course)
indegree[course] += 1

Common Mistake

错误方向：

graph[course].append(prerequisite)

这会把 dependency order 反过来。

👉 面试回答

Topological sort 最重要的实现细节之一是 edge direction。

如果 b 是 a 的 prerequisite，那么 edge 应该是 b → a。

意思是完成 b 之后，a 才可能被解锁。

Edge direction 写反是 Course Schedule 这类题最常见 bug。

7️⃣ Course Schedule I

Problem

给定课程和 prerequisites，判断是否能完成所有课程。

Key Insight

这是 directed graph cycle detection。

如果有 cycle，
courses 互相依赖，
就不可能完成。

Code With Kahn’s Algorithm

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    return completed == num_courses

👉 面试回答

Course Schedule 是 directed graph cycle detection。

我会把 edge 建成 prerequisite → course。

然后用 indegree-based topological sorting。

如果所有 courses 都能被 process，说明没有 cycle。

如果有 courses 一直无法被 process，说明 graph 中存在 cycle，无法完成所有课程。

8️⃣ Course Schedule II

Problem

返回完成所有课程的一种 valid order。

如果不可能，返回 empty list。

Code

from collections import deque

def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    order = []

    while queue:
        course = queue.popleft()
        order.append(course)

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    if len(order) != num_courses:
        return []

    return order

Key Difference

Course Schedule I 问：

Can we finish?

Course Schedule II 问：

What is one valid order?

👉 面试回答

Course Schedule II 和 Course Schedule I 是同一个 topological sort pattern。

区别是这里需要返回具体 order。

我把每个处理过的 course 放入 order。

如果最终 order 长度等于课程数，它就是 valid topological order。

否则存在 cycle，返回 empty list。

9️⃣ DFS-Based Topological Sort

Core Idea

DFS 也可以产生 topological order。

对每个 node：

先 visit 所有 descendants
再把 current node 加入 result

这是 postorder。

最后 reverse result。

Node States

使用三种状态：

= unvisited
= visiting
= visited

如果 DFS 遇到 visiting node：

cycle detected

Code

def topo_sort_dfs(n, edges):
    graph = [[] for _ in range(n)]

    for a, b in edges:
        graph[a].append(b)

    state = [0] * n
    order = []

    def dfs(node):
        if state[node] == 1:
            return False

        if state[node] == 2:
            return True

        state[node] = 1

        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False

        state[node] = 2
        order.append(node)
        return True

    for node in range(n):
        if state[node] == 0:
            if not dfs(node):
                return []

    order.reverse()
    return order

👉 面试回答

DFS-based topological sort 使用 postorder traversal。

我先访问当前 node 的所有 neighbors，然后把当前 node 加入 order。

最后 reverse postorder result。

为了检测 cycle，我使用三种状态： unvisited、visiting 和 visited。

如果 DFS 遇到 visiting node，说明存在 cycle。

🔟 Kahn vs DFS Topological Sort

Kahn’s Algorithm

使用：

indegree + queue

适合：

finding valid order
detecting cycles by processed count
level-style dependency processing

DFS Topological Sort

使用：

recursion + postorder

适合：

cycle detection
dependency recursion
postorder reasoning

Comparison

Approach	Data Structure	Cycle Detection	Output
Kahn	Queue + indegree	processed count < n	direct order
DFS	Recursion + states	visiting node found	reverse postorder

👉 面试回答

Kahn’s algorithm 使用 indegree 和 queue。

DFS topological sort 使用 recursion 和 postorder。

两者复杂度都是 O(V + E)。

如果我要直接得到 dependency order，我通常更倾向 Kahn’s algorithm。

如果题目更强调 recursion 或 cycle detection， DFS 写法也很自然。

1️⃣1️⃣ Cycle Detection

为什么 Cycle 会破坏 Topological Sort？

Example:

A → B
B → C
C → A

这意味着：

A before B
B before C
C before A

不可能同时满足。

Kahn’s Cycle Detection

如果 queue 为空，但还没有处理所有 nodes：

cycle exists

因为剩下的 nodes indegree 都无法归零。

DFS Cycle Detection

如果 DFS 遇到当前 recursion stack 中的 node：

cycle exists

这个 node 的状态是：

visiting

👉 面试回答

如果 directed graph 有 cycle，就不存在 topological order。

使用 Kahn’s algorithm 时，如果最后 processed count 小于 node count，说明存在 cycle。

使用 DFS 时，如果访问到 state 为 visiting 的 node，说明存在 cycle。

1️⃣2️⃣ Alien Dictionary

Problem

给定按照未知字母表排序的 words，推导 characters 的顺序。

Example:

["wrt", "wrf", "er", "ett", "rftt"]

一个 valid output：

"wertf"

Key Insight

比较相邻 words。

找到第一个不同 character。

wrt
wrf

First difference:

t before f

所以 edge：

t → f

Invalid Prefix Case

["abc", "ab"]

Invalid，因为更长的 word 出现在自己的 prefix 前面。

Code

from collections import deque

def alien_order(words):
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]

        if len(word1) > len(word2) and word1.startswith(word2):
            return ""

        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    indegree[c2] += 1
                break

    queue = deque([char for char in indegree if indegree[char] == 0])
    order = []

    while queue:
        char = queue.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(indegree):
        return ""

    return "".join(order)

👉 面试回答

Alien Dictionary 可以建模成 topological sort。

每个 character 是一个 node。

通过比较相邻 words，可以推导出字符之间的 ordering constraint。

第一个不同的 character 产生一条 directed edge。

然后运行 topological sort。

如果有 cycle 或 invalid prefix case，说明不存在 valid order。

1️⃣3️⃣ Minimum Height Trees

Problem

给定一棵 undirected tree，找所有能产生 minimum height 的 roots。

为什么像 Topological BFS？

这个题不是标准 directed topological sort，但用了类似 degree trimming 的思想。

Leaves 的 degree 是 1。

不断移除 leaves。

最后剩下的 center nodes 就是答案。

Code

from collections import deque

def find_min_height_trees(n, edges):
    if n == 1:
        return [0]

    graph = [set() for _ in range(n)]

    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)

    leaves = deque()

    for node in range(n):
        if len(graph[node]) == 1:
            leaves.append(node)

    remaining = n

    while remaining > 2:
        size = len(leaves)
        remaining -= size

        for _ in range(size):
            leaf = leaves.popleft()
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)

            if len(graph[neighbor]) == 1:
                leaves.append(neighbor)

    return list(leaves)

👉 面试回答

Minimum Height Trees 不是标准 topological sort，因为 graph 是 undirected。

但它使用了类似 degree-based trimming 的思想。

我们从 leaves 开始一层一层向内剥离。

最后剩下的一个或两个 nodes 是 tree centers，它们作为 root 时可以产生 minimum height。

1️⃣4️⃣ Task Scheduling

Problem Pattern

给定 tasks 和 dependencies，返回一个 valid execution order。

Example:

A before C
B before C
C before D

Valid order:

A, B, C, D

or:

B, A, C, D

Topological Sort Model

Task = node
Dependency = directed edge
No dependency = indegree 0

Key Insight

没有 prerequisites 的 tasks 可以先开始。

完成一个 task 后，它依赖的后续 tasks 可能变得 available。

👉 面试回答

Task scheduling 是天然的 topological sort 问题。

每个 task 是一个 node。

每个 dependency 是从 prerequisite 指向 dependent task 的 directed edge。

Indegree 为 0 的 tasks 可以先执行。

执行一个 task 后，它的 dependents 的 indegree 会减少。

1️⃣5️⃣ Build System Dependency Order

Example

假设：

parser must build before compiler
compiler must build before optimizer
optimizer must build before runtime

Edges:

parser → compiler
compiler → optimizer
optimizer → runtime

Valid build order:

parser, compiler, optimizer, runtime

If There Is a Cycle

compiler → optimizer
optimizer → compiler

这意味着：

compiler needs optimizer
optimizer needs compiler

没有 valid build order。

👉 面试回答

Build system 经常使用 dependency graph。

每个 module 是一个 node。

每个 dependency 是 directed edge。

Topological sort 可以产生 valid build order。

如果 graph 中有 cycle， build dependencies 是 invalid 的。

1️⃣6️⃣ Topological Sort With Multiple Valid Answers

Important Note

Topological order 不一定唯一。

Example:

A → C
B → C

Valid orders:

A, B, C
B, A, C

Why?

A 和 B 初始 indegree 都是 0。

它们谁先处理都可以。

Interview Implication

如果题目说：

return any valid order

任意 topological order 都可以。

如果题目说：

lexicographically smallest order

使用 min-heap 替代 queue。

👉 面试回答

Topological order 可能不唯一。

当多个 nodes 的 indegree 都是 0 时，它们都可以作为下一个处理节点。

如果题目只要求 any valid order，返回任意一个即可。

如果要求 lexicographically smallest order，我会用 min-heap 替代 queue。

1️⃣7️⃣ Lexicographically Smallest Topological Order

Problem

返回 node value 或 character 的最小 topological order。

Key Change

用 min-heap 替代 queue：

import heapq

这样每次选择当前可用 nodes 中最小的。

Code

import heapq

def topo_sort_lexicographically_smallest(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1

    heap = []

    for node in range(n):
        if indegree[node] == 0:
            heapq.heappush(heap, node)

    order = []

    while heap:
        node = heapq.heappop(heap)
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                heapq.heappush(heap, neighbor)

    if len(order) != n:
        return []

    return order

👉 面试回答

如果多个 valid topological orders 存在，且题目要求最小 order，我会把 queue 换成 min-heap。

Heap 每次选择当前所有 indegree 为 0 的 nodes 中最小的。

其余逻辑仍然和 Kahn’s algorithm 一样。

1️⃣8️⃣ Topological Sort vs BFS

Relationship

Kahn’s algorithm 看起来像 BFS。

它使用：

queue
level-style processing
neighbor expansion

但含义不同。

BFS

Queue 存的是：

按 source distance 分层的 nodes

Kahn’s Algorithm

Queue 存的是：

没有剩余 prerequisites 的 nodes

👉 面试回答

Kahn’s algorithm 看起来像 BFS，因为它也使用 queue。

但 BFS 的 queue 是按 distance from source 组织的。

Topological sort 的 queue 是按 dependency readiness 组织的。

一个 node 进入 queue，是因为它的 indegree 变成 0，而不是因为它距离 source 更近。

1️⃣9️⃣ Topological Sort vs DFS

DFS Traversal

DFS 深度优先探索：

node → neighbor → neighbor's neighbor

DFS Topological Sort

DFS topological sort 使用 postorder：

先处理 descendants
再加入 current node

Key Difference

普通 DFS 得到的是 traversal order。

DFS topological sort 得到的是 reverse postorder 的 dependency order。

👉 面试回答

普通 DFS traversal order 不一定是 topological order。

对 DFS-based topological sort，我会在所有 descendants 都处理完后，再把当前 node 加入结果。

最后 reverse postorder，得到 topological order。

2️⃣0️⃣ Complexity Analysis

Time Complexity

对于 V 个 vertices 和 E 条 edges：

O(V + E)

因为：

build graph: O(E)
process each node once: O(V)
process each edge once: O(E)

Space Complexity

O(V + E)

用于：

graph adjacency list
indegree array
queue or recursion stack
result order

Heap Version

如果使用 min-heap：

O((V + E) log V)

因为 heap operations 是：

O(log V)

👉 面试回答

Topological sort 的复杂度是 O(V + E) time 和 O(V + E) space。

每个 node 处理一次，每条 edge 检查一次。

如果用 heap 来保证 lexicographically smallest order，复杂度会变成 O((V + E) log V)。

2️⃣1️⃣ 常见 Edge Cases

No Edges

n = 3
edges = []

任意 order 都 valid：

[0, 1, 2]

Single Node

n = 1

Order:

[0]

Cycle

0 → 1
1 → 0

没有 valid order。

根据题目返回：

[]
False
""

Disconnected DAG

0 → 1
2 → 3

需要处理所有 components。

Duplicate Edges

Duplicate edges 可能错误地让 indegree 增加多次。

如果 input 可能有 duplicates，要处理。

Invalid Prefix in Alien Dictionary

["abc", "ab"]

Invalid。

👉 面试回答

常见 edge cases 包括 no edges、single node、cycle、disconnected DAG、duplicate edges，以及 Alien Dictionary 中的 invalid prefix。

我会确保初始化所有 nodes，包括没有出现在 edges 中的 isolated nodes。

2️⃣2️⃣ 常见错误

Mistake 1: Edge Direction 错误

Prerequisite 应该是：

prerequisite → course

而不是：

course → prerequisite

Mistake 2: 忘记没有 Edges 的 Nodes

所有 nodes 都要初始化。

没有 prerequisites 的 course 也应该出现在结果中。

Mistake 3: 没有检测 Cycle

需要检查：

len(order) == n

或者用 DFS states。

Mistake 4: Duplicate Edge Bug

如果 duplicate edges 存在：

a → b
a → b

indegree 可能被错误增加两次。

必要时用 set。

Mistake 5: 混淆 BFS Shortest Path 和 Topological Sort

两者都可能用 queue，但 queue 的含义不同。

👉 面试回答

Topological sort 常见错误包括： edge direction 写反、忘记 isolated nodes、没有检查 cycle、 duplicate edges 处理错误、以及把 Kahn’s queue 和 BFS distance queue 混淆。

我通常会先明确： edge 到底表示什么 dependency。

2️⃣3️⃣ 什么时候 Topological Sort 适用？

Good Fit

当题目问：

dependency ordering
prerequisite scheduling
build order
task execution order
valid ordering with constraints
detecting impossible dependency cycles
DAG ordering

Problem Signals

看到这些关键词时想到 topological sort：

prerequisite
dependency
before
after
course schedule
build order
tasks
workflow
must happen before
alien dictionary

👉 面试回答

当问题涉及 directed dependencies 时，我会考虑 topological sort。

如果一些 tasks 必须在另一些 tasks 之前完成，或者需要判断 dependency cycle 是否让任务 impossible， topological sort 通常是正确模式。

2️⃣4️⃣ 什么时候 Topological Sort 不适用？

Not Good Fit

Topological sort 不适合：

graph is undirected
dependencies can contain valid cycles
need shortest path
need minimum cost
need all possible orders
need dynamic updates frequently

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Undirected components	DFS / BFS / Union Find
Need all valid orders	Backtracking + topological constraints
Dynamic dependency updates	Specialized graph data structure
Minimum spanning tree	Kruskal / Prim

👉 面试回答

Topological sort 适用于 directed acyclic dependency graph。

如果 graph 是 undirected，或者问题问 shortest path、minimum cost， topological sort 通常不是正确工具。

如果需要所有 valid orders，可能需要在 topological constraints 上做 backtracking。

2️⃣5️⃣ 标准模板

Kahn’s Algorithm Template

from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for pre, nxt in edges:
        graph[pre].append(nxt)
        indegree[nxt] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != n:
        return []

    return order

Course Schedule Template

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    return completed == num_courses

DFS Topological Sort Template

def topo_sort_dfs(n, edges):
    graph = [[] for _ in range(n)]

    for pre, nxt in edges:
        graph[pre].append(nxt)

    state = [0] * n
    order = []

    def dfs(node):
        if state[node] == 1:
            return False

        if state[node] == 2:
            return True

        state[node] = 1

        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False

        state[node] = 2
        order.append(node)
        return True

    for node in range(n):
        if state[node] == 0:
            if not dfs(node):
                return []

    order.reverse()
    return order

Alien Dictionary Template

from collections import deque

def alien_order(words):
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]

        if len(word1) > len(word2) and word1.startswith(word2):
            return ""

        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    indegree[c2] += 1
                break

    queue = deque([char for char in indegree if indegree[char] == 0])
    order = []

    while queue:
        char = queue.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(indegree):
        return ""

    return "".join(order)

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Topological sort 用于对 directed graph 中有 dependency 的 nodes 进行排序。

如果有 edge A → B，表示 A 必须出现在 B 前面。

Topological sort 只适用于 directed acyclic graph。如果 graph 有 cycle，就不存在 valid topological order。

最常见实现是 Kahn’s algorithm。它使用 indegree array 和 queue。

Indegree 表示一个 node 还有多少 remaining prerequisites。 Indegree 为 0 的 nodes 没有剩余依赖，所以可以先处理。

处理一个 node 后，我们减少它 neighbors 的 indegree。如果某个 neighbor 的 indegree 变成 0，就加入 queue。

如果所有 nodes 都被处理，就得到了 valid topological order。如果无法处理所有 nodes，说明 graph 中有 cycle。

另一种方式是 DFS-based topological sort。 DFS 先访问所有 descendants，然后把当前 node 加入 postorder list。 Reverse postorder 就是 topological order。

DFS 也可以用三色状态检测 cycle： unvisited、visiting、visited。如果 DFS 遇到 visiting node，说明存在 cycle。

Course Schedule 是经典 topological sort 题。 Courses 是 nodes， prerequisites 是 directed edges。如果存在 cycle，说明课程之间互相依赖，无法完成所有课程。

Alien Dictionary 也是 topological sort。 Characters 是 nodes。通过比较相邻 words 的第一个不同字符，推导出 ordering constraints。然后对 characters 做 topological sort。

一个关键实现细节是 edge direction。如果 b 是 a 的 prerequisite， edge 应该是 b → a，而不是 a → b。

Topological order 不一定唯一。如果多个 nodes 同时 indegree 为 0，它们都可以作为下一个 node。如果题目要求 lexicographically smallest order，我会用 min-heap 替代 queue。

Topological sort 的复杂度是 O(V + E)，因为每个 node 和 edge 都只处理一次。

高级工程师解释时，我会讲清楚： node 代表什么， directed edge 代表什么 dependency， indegree 如何表示 remaining dependencies，如何检测 cycle，以及为什么 topological sort 只适用于 DAG。

⭐ Final Insight

Topological Sort 的核心不是“排序”。

它的核心是 dependency readiness。

Senior-level 的重点是：

node 是什么， edge 方向代表什么， indegree 表示什么，哪些 node 已经没有 remaining prerequisites，如何检测 cycle，以及为什么只有 DAG 才存在 valid order。

能讲清楚这些， Topological Sort 就是一种解决 dependency ordering 和 cycle detection 的核心图算法模式。