NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 17 题

关于拓扑排序，下列说法正确的是(   )。

这题考拓扑排序的基本性质，拿到选项先看反例：有环图、多起点图、唯一性，逐一排除就能锁定正确答案。

学生最容易把“入度为0的结点”和“序列中排在最前面的结点”混为一谈，以为只要入度为0就一定排在最前；或者误以为连通图都能拓扑排序、拓扑序列一定唯一。其实多个入度为0的结点谁先谁后都可以，只要不破坏“前驱在前”的规则就行。

考点与概念 拓扑排序是对有向无环图（DAG）的一种线性排列，要求若存在边 u→v，则 u 在序列中一定出现在 v 之前。实现上常用 Kahn 算法：不断取出当前入度为 0 的结点输出，再把它的后继入度减 1，重复直到图空或剩下环。

命题视角 命题人喜欢挖三个坑：一是用“连通”代替“无环”，让学生误以为所有连通有向图都能拓扑排序；二是强调“唯一”，其实只要图里有两个入度为 0 的结点，它们的先后顺序可以互换，序列就不唯一；三是把“入度为 0 的结点”和“序列第一个结点”偷换概念，诱导学生选 C。

逐项分析 A 错。拓扑排序的前提是图无环，连通只是描述边的覆盖范围，有环的连通图（比如 1→2→1）根本排不出来。 B 错。只要图里存在多个入度为 0 的结点，或者在某个时刻有多个可选的入度为 0 结点，它们的相对顺序可以任意，因此拓扑序列通常不唯一。 C 错。入度为 0 的结点确实必须排在它所有后继之前，但“总会排在入度大于 0 的结点前面”这句话太绝对。当图中有多个入度为 0 的结点时，它们之间的先后可以互换，而它们后面紧跟着的结点入度可能已经变成 0，所以不能说“入度 0 的结点总是排在所有入度 > 0 的结点前面”。 D 对。拓扑排序的第一步只能选入度为 0 的结点，因为任何有入边的结点都有前驱，前驱还没输出就不能输出它。因此序列的第一个结点必然是入度为 0 的点。

考频与趋势 拓扑排序在历年初赛中出现过 8 次，覆盖 2009–2025 共 17 年。逐年分布：2009 年 1 题、2010 年 2 题、2017 年 1 题、2023 年 3 题、2025 年 1 题；分赛事：NOIP 提高组 初赛 3 题、CSP 提高级 3 题、NOIP 普及组 初赛 1 题、CSP 入门级 1 题。从数据看，近年（2023–2025）出题频率明显上升，且集中在提高组和高阶 CSP，说明命题人更倾向于用拓扑排序考察算法基础。

预测 基于现有数据，未来一两年内拓扑排序仍可能作为单选或多选中的概念题出现，大概率继续聚焦“无环性”“唯一性”“入度为 0 结点的位置”这几个易错点。暂无足够依据预测是否会突然变成算法大题，但复习时建议把 Kahn 算法的手写过程练熟，以防万一。