🏷️ 知识点：有向无环图
用有向无环图描述表达式 (x+y)*((x+y)/x)，需要的顶点个数至少是（ ）。
A. 5 B. 6 C. 8 D. 9
[tag_link]
正确答案：A
把相同的变量和公共子表达式只存一次：叶结点 x、y 各 1 个，x+y 共用 1 个加法结点，再加除法结点和最外层乘法结点，共 2+1+1+1=5 个顶点。不能把两处 x+y 分别建树，也不能把两处 x 分开存储，因此最少为 5，选 A。对应 DAG 如下：
如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有的 1 都集中到对角线以上？
[tag_link]
参考答案
对该 DAG 进行拓扑排序，并按拓扑序列依次编号为 1,2,…,n。对任意弧 i→j，拓扑序都要求 i 排在 j 之前，因此新编号满足 i<j；对应的邻接矩阵元素 A[i][j] 只可能位于主对角线上方。拓扑排序可用入度为 0 的顶点逐步删除，若有多个候选顶点，任取其一即可。
推导
DAG 必然存在拓扑序。重新编号后，若矩阵下三角位置 A[i][j]（i>j）为 1，就表示存在弧 i→j，与拓扑序中 i 应排在 j 前矛盾。因此所有 1 均在主对角线上方；该性质不要求拓扑序唯一。
易错点
只按原编号排序不一定成立；必须使用拓扑序。矩阵上三角方向取决于约定的弧方向和编号顺序，本文约定 A[i][j]=1 表示 i→j。
已知有向图 G=(V,E)，其中 V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}，E={⟨v₁,v₂⟩,⟨v₁,v₃⟩,⟨v₁,v₄⟩,⟨v₂,v₅⟩,⟨v₃,v₅⟩,⟨v₃,v₆⟩,⟨v₅,v₇⟩,⟨v₆,v₇⟩,⟨v₄,v₆⟩}，G 的拓扑序列是（ ）。
A. {v₁,v₃,v₄,v₆,v₂,v₅,v₇} B. {v₁,v₃,v₂,v₆,v₄,v₅,v₇} C. {v₁,v₃,v₄,v₅,v₂,v₆,v₇} D. {v₁,v₂,v₅,v₃,v₄,v₆,v₇}
正确答案：A
结论
A 满足所有有向边的起点先于终点，是合法拓扑序列。
推导
逐项验证边约束：v₁ 在 v₂、v₃、v₄ 之前；v₂、v₃ 在 v₅之前；v₃、v₄ 在 v₆之前；v₅、v₆ 在 v₇之前。A 的位置顺序全部满足这些约束。
易错点
A 正确；B 将 v₆ 放在 v₄ 前违反 v₄→v₆；C 将 v₅ 放在 v₂ 前违反 v₂→v₅；D 将 v₅ 放在 v₃ 前违反 v₃→v₅。
试编写利用 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)（不计图本身）。