第 71 题
试编写利用 DFS 实现有向无环图拓扑排序的算法。
[tag_link]
参考答案
用三色标记区分顶点状态：白色表示未访问，灰色表示仍在当前 DFS 递归栈中，黑色表示其所有后继都已处理。遇到指向灰色顶点的边就是回边，说明图中有环，不能得到拓扑序。
topologicalSort(G):
color[v] = WHITE for every vertex v
stack = empty
for each vertex v:
if color[v] == WHITE and not dfs(v):
return "图中有环"
return pop all vertices from stack
dfs(u):
color[u] = GRAY
for each v in Adj[u]:
if color[v] == GRAY:
return false
if color[v] == WHITE and not dfs(v):
return false
color[u] = BLACK
push u into stack
return true
顶点 u 只有在所有后继完成后才入栈，因此对任意边 u→v，v 先于 u 入栈；最后按出栈顺序输出，就得到完成时间从晚到早的拓扑序。外层循环遍历所有白色顶点，因此也适用于不连通的 DAG。
采用邻接表时，每个顶点和每条边只处理常数次，时间复杂度为 O(V+E)，辅助空间为 O(V)（不计图本身）。