DFS 后序拓扑排序
运行 DFS，在一个节点的所有邻居都完成探索后将其压入栈中，然后弹出栈以得到有效的拓扑序。
DFS 后序拓扑排序 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
基于 DFS 的拓扑排序思路
第二种经典的拓扑排序算法使用带后序处理的 DFS。在完全探索一个节点的所有邻居（以及它们的后代）之后，将该节点压入栈中。当所有节点都处理完毕后，弹出栈即可读取拓扑顺序。一个节点在其所有依赖项都处理完之后才被压入栈，意味着它会在顺序中排在前面——因此，反转后序顺序就是拓扑排序结果。
后序处理背后的直觉
考虑一个依赖图，其中课程 A 需要先修课程 B。当 DFS 访问 A 时，会先递归访问 B。B 没有先修课程，因此会先完成并首先被压入栈中。随后 A 完成并被压入栈中。弹出栈时，输出结果中 A 会排在 B 前面——但我们会在最后反转顺序，从而得到 B 在 A 前面：先学习 B，再学习 A。后序处理会先压入依赖项，再压入依赖它们的节点，因此反转后的栈就是有效的拓扑顺序。
用于环检测的三色 DFS
为已访问状态使用三种颜色：WHITE (0) = 未访问，GREY (1) = 当前正在处理（位于 DFS 调用栈中），BLACK (2) = 已完全处理。回边——指向 GREY 节点的边——表示存在环。指向 BLACK 节点的边是安全的（这些节点已经被完全探索）。这种三色方案可以正确检测有向图中的所有环。
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)完整的 DFS 拓扑排序实现
使用递归 DFS 为节点着色，按后序将节点压入栈中，并在检测到环时返回假值。访问完所有节点后，反转栈即可得到拓扑顺序。
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))使用迭代 DFS 避免栈溢出
对于大型图，Python 的递归深度限制（默认值为 1000）是一个需要关注的问题。使用显式栈的迭代 DFS可以避免这一问题。关键做法是：首先压入 (node, False)；弹出且值为 False 时，压入 (node, True)（表示“探索完成后我会回到这里”），再将所有未访问的邻居与 False 一起压入。弹出且值为 True 时，将该节点标记为 BLACK，并将其压入结果栈。
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS 与 Kahn 算法：比较
两者的时间复杂度都是O(V + E)。主要区别是：Kahn 算法（BFS）会自然地产生按依赖项最早出现顺序排列的节点，并且环检测更简单（检查长度即可）。DFS 后序处理以递归方式工作，并显式检测回边。如果希望结果直接按正向顺序排列而无需反转，通常优先使用 Kahn 算法。如果还需要完整的后序顺序来完成其他任务（例如检测 SCC），则更适合使用 DFS。在面试中，两种方法都可以接受。
树与 DAG 中的后序处理
在树中，后序遍历依次访问左子树 → 右子树 → 根节点。在 DAG 中，后序 DFS 会先访问一个节点的所有依赖项，再处理节点本身——这是对多个前驱节点和任意图结构的相同思想进行推广。DFS 树的根节点（起始节点）会在其后代节点中最后被压入栈，因此在反转后的栈中排在最前面——这正是一个没有前驱节点的节点应处于的拓扑位置。
外星字典（LeetCode 269）
外星字典：给定一组按外星语言排序的单词，推导字符的排序顺序。逐个字符比较相邻单词，找出第一个不同的位置——这会产生一条边 c1 → c2，表示 c1 排在 c2 前面。收集所有这样的边，然后运行拓扑排序，生成外星字符的排序顺序。如果存在环，则该排序无效。
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'带约束的拓扑排序
有些问题要求拓扑排序满足额外约束，例如保持原始列表中元素的相对顺序。可以将 Kahn 算法与自定义优先队列或预排序结合起来：在每一步对队列中的内容使用稳定排序，从而保持元素原有的相对顺序。这些带约束的变体考查对算法灵活性的更深入理解。
识别拓扑排序问题
面试题中表示需要使用拓扑排序的提示语包括：“给定依赖关系”、“先修条件”、“任务排序”、“构建顺序”、“能否完成所有任务？”、“找出一个有效序列”。如果问题涉及对元素进行排序，并且某些元素必须排在其他元素之前，就应建立有向图并应用 Kahn 算法或 DFS 拓扑排序。同一个问题中通常还会要求检测环。
比较 DFS 与 Kahn 算法的输出
对于同一个图，DFS 和 Kahn 算法可能生成不同的有效拓扑顺序。两者都是正确的——一个 DAG 可能存在多个有效的拓扑顺序。要验证结果是否正确，请检查图中的每条边 u → v，确保输出顺序中 u 都排在 v 前面。对于要求特定顺序的面试题（例如字典序最小），应使用带最小堆的 Kahn 算法——DFS 后序处理不会自然地产生字典序最小的顺序。
快速检查
测试您对本课中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
本课中您学到了：基于 DFS 的后序拓扑排序会在所有依赖项都探索完成后压入节点，三色标记（WHITE/GREY/BLACK）通过检测指向 GREY 节点的回边来检测环，以及反转后序栈可以得到有效的拓扑顺序。接下来，我们会将拓扑排序直接应用于课程安排问题 I 和 II。
常见问题解答
「DFS 后序拓扑排序」课时是免费的吗？
是的 — 「DFS 后序拓扑排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「DFS 后序拓扑排序」这节课中我会学到什么？
运行 DFS，在一个节点的所有邻居都完成探索后将其压入栈中，然后弹出栈以得到有效的拓扑序。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「DFS 后序拓扑排序」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。