GESP 七级 · GESP 202509 C++ 七级 第 25 题

很多游戏中为玩家设置多种可供学习的技能，要学习特定技能又往往需要先学习 1 个或以上的前置技能。尽管这样的技能间依赖关系常被玩家称为“技能树”，但它并不一定是树，更可能是有向无环图。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】有向无环图(DAG)｜树结构特性｜技能依赖建模

1. 🎯 考纲定位

• GESP 7 级"数据结构与算法"模块核心考点
• 命题人卡住的是玩家直觉与数学定义的偏差：现实中技能依赖常被口误称为"树"，但严格来说必须是无环的

2. 🧠 解题思维

• 看到"依赖关系"先想：方向性（前置→后置）+ 环状性（能否回头学）
• 树要求单根且无环，但技能树常有多根（不同技能线）且无环
• 题干已明示"不一定是树"，再结合"更可能是有向无环图"——这正是 DAG 的定义特征

3. 🪤 陷阱拆解

• 选项 B 设计动机：利用"树"的日常语义误导（玩家说的"技能树"≠数学树）
• 题干中"不一定是树"是绝对化表述，但结合"更可能是 DAG"实则精准
• 若只背"树=有根无环"而忽略"多根"场景，就会误判为错误

4. 🔄 反命题思维

• 若把"有向无环图"改为"无向图"，答案必变（技能依赖必须单向）
• 刷到类似题时，先问：这是否允许多父节点？是否必须无环？