如何在 Java 中利用数组实现简单的拓扑排序（Topological Sort）中的入度表记录

如何在 Ja va 中利用数组实现简单的拓扑排序（Topological Sort）中的入度表记录

在 Ja va 里用数组来实现拓扑排序的入度表，其实是个既简洁又高效的做法。它的核心思路，就是用一个整型数组 inDegree[] 来记录每个节点当前的“入度”——也就是有多少条边指向它。这种方法特别适合节点编号连续（比如从 0 到 n-1）的有向无环图，省去了复杂数据结构的开销。

一、入度数组的定义与初始化

假设我们处理的图有 n 个顶点，编号正好是 0 到 n−1。第一步很简单，声明一个长度同样为 n 的整型数组：

int[] inDegree = new int[n];

初始化之后，数组里所有元素默认都是 0，这表示还没有统计任何入边。接下来的工作，就是遍历图中的所有有向边 u → v，每遇到一条，就对 inDegree[v] 执行一次加一操作。遍历完成，入度数组也就构建好了。

话说回来，如果想系统提升，不妨参考一下这份“Ja va免费学习笔记（深入）”。

二、从邻接表或边列表构建入度数组

实际编码时，图的输入形式通常有两种，处理上稍有区别：

• 如果拿到的是邻接表，比如 List> graph（其中 graph[u] 存储了节点 u 的所有后继节点），那么构建过程就是两层循环：先遍历每个节点 u，再遍历它的每个邻居 v，并对 inDegree[v]++。
• 如果直接给的是边列表，例如 int[][] edges = {{0,1},{1,2},{0,2}}，那就更直接了：遍历每条边 edges[i][0] → edges[i][1]，然后对目标节点 edges[i][1] 对应的下标执行 inDegree[edges[i][1]]++ 即可。

三、配合队列实现 Kahn 算法（标准拓扑排序）

光有入度数组还不够，它本身并不产生排序。真正的排序逻辑，需要配合队列，也就是经典的 Kahn 算法：

• 首先，扫描一遍入度数组，把所有 inDegree[i] == 0 的节点 i 放入队列。这些节点就是当前没有任何前置依赖的“起点”。
• 接着，从队列中取出一个节点 u，将它加入最终的拓扑序列。
• 然后，遍历 u 的每一个后继节点 v，将 inDegree[v] 减 1。你猜怎么着？如果减完之后 inDegree[v] 变成了 0，那就意味着 v 的所有前驱都已被处理，可以立即将它入队，等待后续处理。

循环这个过程，直到队列为空。最后，检查一下拓扑序列的长度是否等于节点总数 n。如果相等，恭喜你，排序成功；如果不相等，那基本可以断定，图中存在环，无法进行拓扑排序。

四、注意事项与边界情况

使用数组记录入度虽好，但有个重要前提：节点编号必须是连续且从0开始的整数。如果节点是字符串，或者编号是稀疏的（比如 100, 200, 999），那就得先做一步映射，把它们转换成 0~n−1 的连续索引，然后再建数组。当然，也可以退一步，直接使用 Map 来灵活存储。

另外，需要特别注意的是，入度数组只负责计数，它并不保存图本身的结构信息。因此，你仍然需要邻接表或邻接矩阵来提供每个节点的后继节点列表，以便在 Kahn 算法中遍历。理解了这一点，才算真正掌握了这个技巧的精髓。