在角色扮演游戏中，技能树是玩家成长的核心系统。某些高级技能要求先掌握多个前置技能，而前置技能之间又可能存在层层依赖。如何设计一个算法，既能正确计算技能的学习顺序，又能及时发现策划配置中的循环依赖错误？这正是拓扑排序（Topological Sort）的经典应用场景。本文用Java完整实现DFS与Kahn两种拓扑排序算法，并深入讲解环检测机制与最长技能路径计算。
一、问题建模：技能树与有向无环图
将每个技能视为图中的一个顶点，若技能A是技能B的前置条件，则添加一条从A指向B的有向边。一个合法的技能树必须满足：
- 不存在循环依赖：若A依赖B、B依赖C，则C不能再依赖A，否则形成环
- 存在有效学习顺序：所有技能可以按照依赖关系线性排列，使得每条边都从排在前面的顶点指向后面的顶点
满足上述条件的图称为有向无环图（DAG, Directed Acyclic Graph）。拓扑排序的目标，就是找到这样一个线性序列。
1.1 核心数据结构
import java.util.*;
/**
* 技能树图：使用邻接表存储有向图
* 每个顶点代表一个技能，有向边代表前置依赖关系
*/
public class SkillGraph {
private final int vertexCount; // 技能总数
private final List<List<Integer>> adj; // 邻接表：adj[u] 表示u指向的所有后继技能
private final List<String> skillNames; // 技能名称，用于输出展示
public SkillGraph(int n, List<String> names) {
this.vertexCount = n;
this.skillNames = new ArrayList<>(names);
this.adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
}
/**
* 添加前置依赖：学习to之前必须先学会from
* 对应有向边 from -> to
*/
public void addPrerequisite(int from, int to) {
adj.get(from).add(to);
}
public int getVertexCount() { return vertexCount; }
public List<Integer> getSuccessors(int u) { return adj.get(u); }
public String getSkillName(int u) { return skillNames.get(u); }
/**
* 计算每个顶点的入度（有多少前置技能）
* Kahn算法的核心预处理步骤
*/
public int[] computeInDegrees() {
int[] inDegree = new int[vertexCount];
for (int u = 0; u < vertexCount; u++) {
for (int v : adj.get(u)) {
inDegree[v]++;
}
}
return inDegree;
}
/**
* 获取反向邻接表：用于求最长路径时追踪前置节点
*/
public List<List<Integer>> getReverseAdj() {
List<List<Integer>> rev = new ArrayList<>();
for (int i = 0; i < vertexCount; i++) rev.add(new ArrayList<>());
for (int u = 0; u < vertexCount; u++) {
for (int v : adj.get(u)) {
rev.get(v).add(u);
}
}
return rev;
}
}
二、DFS拓扑排序：深度优先与回溯标记
DFS拓扑排序的核心思想是：一个顶点的所有后继顶点必须先于它被输出。利用递归的天然栈结构，我们可以在回溯时将顶点加入结果序列的头部。
2.1 三色标记法与环检测
环检测是拓扑排序不可或缺的一环。我们使用三种颜色标记顶点状态：
- 白色（0）：未访问
- 灰色（1）：正在访问（递归栈中）
- 黑色（2）：已完成访问
如果在DFS过程中遇到一个灰色顶点，说明存在从当前顶点出发回到自身的路径，即图中存在环。
/**
* DFS拓扑排序实现
* 时间复杂度: O(V + E)
* 空间复杂度: O(V)
*/
public class DFSTopologicalSort {
// 颜色定义：0=白色(未访问), 1=灰色(访问中), 2=黑色(已完成)
private static final int WHITE = 0, GRAY = 1, BLACK = 2;
private final boolean hasCycle;
private final List<Integer> order;
public DFSTopologicalSort(SkillGraph graph) {
int n = graph.getVertexCount();
int[] color = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // 用栈模拟结果逆序
boolean[] cycleFlag = { false };
for (int u = 0; u < n; u++) {
if (color[u] == WHITE) {
dfs(graph, u, color, stack, cycleFlag);
}
}
this.hasCycle = cycleFlag[0];
this.order = new ArrayList<>();
// 栈顶元素是最后完成的，依次弹出即得拓扑序
while (!stack.isEmpty()) {
order.add(stack.pop());
}
}
/**
* 深度优先搜索
* @param u 当前访问的顶点
* @param color 颜色标记数组
* @param stack 用于存储完成顺序的栈
* @param cycleFlag 环检测标记（数组实现引用传递）
*/
private void dfs(SkillGraph graph, int u, int[] color,
Deque<Integer> stack, boolean[] cycleFlag) {
color[u] = GRAY; // 标记为访问中
for (int v : graph.getSuccessors(u)) {
if (color[v] == GRAY) {
// 遇到灰色节点，发现回边，存在环
cycleFlag[0] = true;
return;
}
if (color[v] == WHITE) {
dfs(graph, v, color, stack, cycleFlag);
if (cycleFlag[0]) return; // 已发现环，提前终止
}
}
color[u] = BLACK; // 标记为已完成
stack.push(u); // 回溯时入栈
}
public boolean hasCycle() { return hasCycle; }
public List<Integer> getOrder() { return order; }
public String getOrderAsString(SkillGraph graph) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.size(); i++) {
if (i > 0) sb.append(" -> ");
sb.append(graph.getSkillName(order.get(i)));
}
return sb.toString();
}
}
2.2 为什么DFS能得到拓扑序？
DFS拓扑排序的正确性建立在 finish time（完成时间）的单调性上：对于任意有向边 u -> v，在DFS过程中只有三种可能：
v在u之前被访问并完成：此时v先于u入栈，最终顺序中v在u之前u在v之前被访问：递归会沿着边到达v，v完成后u才完成，依然v先于u入栈v是u的祖先（灰色节点）：此时存在环，拓扑排序不存在
因此，按完成时间逆序排列，必然满足所有边的方向约束。
三、Kahn算法：基于入度的BFS策略
Kahn算法采用另一种视角：每次选择入度为0的顶点输出，然后将其所有后继顶点的入度减1。重复此过程直到所有顶点都被输出，或不存在入度为0的顶点（后者说明有环）。
/**
* Kahn拓扑排序实现（BFS-based）
* 时间复杂度: O(V + E)
* 空间复杂度: O(V)
*/
public class KahnTopologicalSort {
private final boolean hasCycle;
private final List<Integer> order;
public KahnTopologicalSort(SkillGraph graph) {
int n = graph.getVertexCount();
int[] inDegree = graph.computeInDegrees();
Queue<Integer> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
// 初始化：将所有入度为0的顶点加入队列
for (int u = 0; u < n; u++) {
if (inDegree[u] == 0) {
queue.offer(u);
}
}
while (!queue.isEmpty()) {
int u = queue.poll();
result.add(u);
// 移除u的所有出边：后继顶点入度减1
for (int v : graph.getSuccessors(u)) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
// 如果输出的顶点数不足，说明存在环
this.hasCycle = result.size() != n;
this.order = result;
}
public boolean hasCycle() { return hasCycle; }
public List<Integer> getOrder() { return order; }
public String getOrderAsString(SkillGraph graph) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.size(); i++) {
if (i > 0) sb.append(" -> ");
sb.append(graph.getSkillName(order.get(i)));
}
return sb.toString();
}
}
3.1 Kahn算法的正确性证明
引理：在DAG中，始终至少存在一个入度为0的顶点。
证明：假设DAG中所有顶点入度都大于0。从任意顶点出发，沿入边反向行走，由于入度大于0，总能找到前驱。但顶点有限，必然重复访问某个顶点，形成环，与DAG定义矛盾。
基于该引理，Kahn算法每次都能安全地移除一个入度为0的顶点。由于移除操作不会在新图中引入环，归纳可知算法能输出全部顶点当且仅当原图为DAG。
四、两种算法对比
| 特性 | DFS拓扑排序 | Kahn算法 |
|---|---|---|
| 核心思想 | 利用完成时间逆序 | 逐层剥离入度为0的顶点 |
| 数据结构 | 递归栈 + 颜色标记 | 队列 + 入度数组 |
| 环检测 | 三色标记发现回边 | 输出顶点数不足 |
| 额外能力 | 天然支持强连通分量(SCC) | 天然支持分层/并行调度 |
| 空间占用 | O(V) 递归栈 | O(V) 队列 |
| 结果稳定性 | 依赖邻接表遍历顺序 | 依赖队列出队顺序 |
| 适用场景 | 需要DFS副产品（如SCC） | 需要按层处理、并行执行 |
在技能树场景中，Kahn算法有一个独特优势：每轮入度为0的技能集合，代表当前可以并行学习的技能组。这在设计游戏UI高亮提示时非常实用。
五、完整测试与验证
public class Main {
public static void main(String[] args) {
// 定义技能名称
List<String> skills = Arrays.asList(
"基础攻击", // 0
"重击", // 1
"旋风斩", // 2
"狂暴", // 3
"盾击", // 4
"铁壁", // 5
"终极审判" // 6
);
SkillGraph graph = new SkillGraph(skills.size(), skills);
// 构建技能依赖关系
graph.addPrerequisite(0, 1); // 基础攻击 -> 重击
graph.addPrerequisite(1, 2); // 重击 -> 旋风斩
graph.addPrerequisite(0, 3); // 基础攻击 -> 狂暴
graph.addPrerequisite(1, 3); // 重击 -> 狂暴
graph.addPrerequisite(0, 4); // 基础攻击 -> 盾击
graph.addPrerequisite(4, 5); // 盾击 -> 铁壁
graph.addPrerequisite(2, 6); // 旋风斩 -> 终极审判
graph.addPrerequisite(3, 6); // 狂暴 -> 终极审判
graph.addPrerequisite(5, 6); // 铁壁 -> 终极审判
System.out.println("=== 技能依赖图 ===");
for (int u = 0; u < graph.getVertexCount(); u++) {
for (int v : graph.getSuccessors(u)) {
System.out.println(" " + skills.get(u) + " -> " + skills.get(v));
}
}
// DFS拓扑排序
DFSTopologicalSort dfsSort = new DFSTopologicalSort(graph);
System.out.println("\n=== DFS拓扑排序 ===");
System.out.println("存在环: " + dfsSort.hasCycle());
System.out.println("学习顺序: " + dfsSort.getOrderAsString(graph));
// Kahn拓扑排序
KahnTopologicalSort kahnSort = new KahnTopologicalSort(graph);
System.out.println("\n=== Kahn拓扑排序 ===");
System.out.println("存在环: " + kahnSort.hasCycle());
System.out.println("学习顺序: " + kahnSort.getOrderAsString(graph));
// 验证：测试含环图
System.out.println("\n=== 环检测测试 ===");
List<String> cycleSkills = Arrays.asList("A", "B", "C");
SkillGraph cycleGraph = new SkillGraph(3, cycleSkills);
cycleGraph.addPrerequisite(0, 1); // A -> B
cycleGraph.addPrerequisite(1, 2); // B -> C
cycleGraph.addPrerequisite(2, 0); // C -> A (形成环)
DFSTopologicalSort dfsCycle = new DFSTopologicalSort(cycleGraph);
KahnTopologicalSort kahnCycle = new KahnTopologicalSort(cycleGraph);
System.out.println("DFS检测到环: " + dfsCycle.hasCycle());
System.out.println("Kahn检测到环: " + kahnCycle.hasCycle());
}
}
输出结果：
=== 技能依赖图 ===
基础攻击 -> 重击
重击 -> 旋风斩
基础攻击 -> 狂暴
重击 -> 狂暴
基础攻击 -> 盾击
盾击 -> 铁壁
旋风斩 -> 终极审判
狂暴 -> 终极审判
铁壁 -> 终极审判
=== DFS拓扑排序 ===
存在环: false
学习顺序: 基础攻击 -> 盾击 -> 铁壁 -> 重击 -> 旋风斩 -> 狂暴 -> 终极审判
=== Kahn拓扑排序 ===
存在环: false
学习顺序: 基础攻击 -> 重击 -> 盾击 -> 旋风斩 -> 狂暴 -> 铁壁 -> 终极审判
=== 环检测测试 ===
DFS检测到环: true
Kahn检测到环: true
注意两种算法得到的拓扑序可能不同，但都是合法解。拓扑排序不唯一，只要满足依赖约束即可。
六、算法扩展：最长技能路径（关键路径）
在实际游戏中，玩家往往关心：从入门到掌握某个终极技能，最少需要学习多少门前置技能？这等价于求DAG中的最长路径问题。
利用拓扑排序的结果，我们可以在线性时间内求解：
/**
* 最长路径计算：基于Kahn拓扑序动态规划
* dp[v] = max(dp[u] + 1) for all u -> v
* 用于计算掌握每个技能所需的最少前置学习步数
*/
public class LongestPath {
public static int[] compute(SkillGraph graph, List<Integer> topoOrder) {
int n = graph.getVertexCount();
int[] dist = new int[n]; // dist[v] 表示到达v的最长路径长度（边数）
Arrays.fill(dist, 0);
List<List<Integer>> revAdj = graph.getReverseAdj();
for (int v : topoOrder) {
for (int u : revAdj.get(v)) {
if (dist[u] + 1 > dist[v]) {
dist[v] = dist[u] + 1;
}
}
}
return dist;
}
public static void printPathLengths(SkillGraph graph, int[] dist) {
System.out.println("\n=== 各技能的最长前置链长度 ===");
for (int i = 0; i < dist.length; i++) {
System.out.println(" " + graph.getSkillName(i) + ": " + dist[i] + " 步");
}
}
}
在技能树场景中，dist[v] 表示学习技能 v 之前必须依次通过的最长依赖链长度。例如”终极审判”的dist值可能为3，意味着玩家至少需要按顺序学习3层前置技能。
七、复杂度总结
| 算法 | 时间复杂度 | 空间复杂度 | 关键数据结构 |
|---|---|---|---|
| DFS拓扑排序 | O(V + E) | O(V) | 递归栈、颜色数组 |
| Kahn拓扑排序 | O(V + E) | O(V) | 队列、入度数组 |
| 最长路径(DAG) | O(V + E) | O(V) | 拓扑序 + 反向邻接表 |
| 强连通分量(SCC) | O(V + E) | O(V) | DFS + Kosaraju/Tarjan |
八、总结
拓扑排序是处理有向依赖关系的基础算法。在技能树、任务系统、编译器依赖解析、数据库迁移脚本执行等领域都有广泛应用。本文实现的DFS和Kahn两种算法各有侧重：DFS更简洁且天然支持SCC分解，Kahn则更直观且易于扩展为分层/并行调度。结合最长路径计算，还能为游戏策划提供”技能解锁深度”等关键数值参考。
读者可以在此基础上进一步探索：
– 字典序最小拓扑序：Kahn算法中使用优先队列替代普通队列
– 并行学习调度：利用Kahn算法的分层特性，计算每轮可并行学习的技能组
– AOV网与AOE网：将技能学习升级为带权边的”时间成本”网络，求解关键路径
