GESP 七级 · GESP 202312 C++ 七级 第 11 题

学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 $G$，有边 $\langle U, V \rangle$ 表示课程 $U$ 是课程 $V$ 的先修课，则要找到某门课程 $C$ 的全部先修课下面哪种方法不可行？（ ）

这题本质是图遍历，拿到题先别想DP，直接建反向图（或正向图找能到的点），从目标课程出发跑BFS或DFS就能把全部先修课搜出来，动态规划在这里纯属画蛇添足。

学生最容易把‘求所有可达点’和‘求最优解’搞混，死记‘图问题用DP'，看到选项D就以为能算出什么最短路径或最大权重，结果发现题目只要求列出课程，根本不需要状态转移。还有人会纠结‘DFS+BFS'是不是更稳妥，其实单纯反向BFS或DFS已足够，混合策略纯属命题人挖的坑。

考点定位：本题考的是图遍历（BFS/DFS）与动态规划适用场景的区别。命题人故意把‘求所有祖先’包装成图论问题，想卡住那些只会背模板、分不清‘遍历’和‘优化’的人。

概念厘清：先修关系是有向边，\langle U, V\rangle 表示U是V的先修。要找课程C的全部先修课，等价于在有向图中找能到达C的所有节点（祖先）。BFS和DFS是标准的图遍历算法，它们的作用就是‘把所有能到的点都走一遍’，不需要任何状态定义或最优性判断。而动态规划（DP）的核心是‘状态转移求最优解’，比如最短路径、最大收益等，必须有一个明确的优化目标。

思考路径：拿到题，第一步建模——把课程当节点，先修关系当有向边。第二步判断目标：题目只要求‘列出全部先修课’，没有‘最少步数’‘最长链’‘最大权重’等字眼。既然没有优化需求，DP的三要素（状态定义、转移方程、初始条件）完全无从下手，强行用DP只会越描越黑。第三步选算法：从C出发，反向遍历（把边反向，从C跑BFS/DFS）或正向遍历（从C跑BFS/DFS找所有能到C的点），两种都行，BFS还能顺便保证顺序，DFS代码更短。选项A、B、C都是遍历类，自然可行；选项D是DP，毫无必要，因此不可行。

陷阱拆解：命题人爱在‘DFS+BFS'这种组合选项里挖坑，暗示需要混合策略，其实单纯反向BFS已足够。更阴险的是D：考生若只背‘图问题用DP'，就会误选‘动态规划’。但DP本质是‘状态转移求最优’，本题只需‘枚举所有可达点’，无优化指标，DP在此处纯属画蛇添足。反命题思维：若题目改为‘求最少先修课数’，则DP（或分层BFS）成为必要；若问‘最长先修链’，则需DFS+DP。刷到此类题先问：命题人想考‘遍历’还是‘优化’？此题显然卡在‘遍历≠DP'的认知偏差上。

考频趋势：图遍历在题库中是高频考点。图形结构共考213题，其中GESP七级就占了78题，说明这类题在七级非常常见。动态规划共考120题，GESP七级有29题，但多数DP题都带有明显的优化目标（如最短路径、最大权重），而本题恰恰是‘无优化’的遍历题，属于DP考纲中的盲区。从历年数据看，单纯‘求所有可达点’这类题在DP分类下几乎没出现过，命题人正是利用这一点制造干扰。

预测：基于当前数据，未来GESP七级仍会高频出现图遍历题，但大概率会继续用‘求全部祖先/后代’这种无优化目标的形式来区分考生对DP适用场景的理解。暂无足够依据预测会出现‘求所有可达点且要求最优顺序’这种混合题型，因为那会模糊‘遍历’与‘DP’的界限，不符合命题人卡认知偏差的套路。