Java数组实现拓扑排序入度表解析

本文深入解析了在Java中如何利用简洁高效的int[]数组实现拓扑排序的核心组件——入度表，从初始化、基于邻接表或边列表构建，到与队列协同执行Kahn算法的完整流程一一道来；不仅阐明了数组下标与节点编号（0~n−1）的直接映射带来的性能优势，还贴心提醒了稀疏编号或非数字节点的处理策略及环检测的关键逻辑，是理解拓扑排序底层实现与工程落地不可多得的实用指南。

在 Java 中用数组实现拓扑排序的入度表，核心是用一个整型数组 inDegree[] 记录每个节点当前的入度（即指向它的边的数量）。这适用于节点编号为 0 到 n-1 的有向无环图（DAG），无需额外数据结构，简洁高效。

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

假设图有 n 个顶点（编号 0 ~ n−1），先声明长度为 n 的整型数组：

int[] inDegree = new int[n];

初始时所有元素为 0，表示尚未统计任何入边。后续遍历图的所有有向边 u → v，对每条边执行 inDegree[v]++ 即可完成构建。

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

常见输入形式有两种，处理方式略有不同：

• 若已知邻接表 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 算法（标准拓扑排序）

入度数组本身不排序，需配合广度优先逻辑：

• 将所有 inDegree[i] == 0 的节点 i 入队（它们是当前可选的起点）；
• 每次出队一个节点 u，将其加入拓扑序列；
• 遍历 u 的每个后继 v，执行 inDegree[v]--；若减后为 0，立即将 v 入队。

若最终拓扑序列长度等于 n，说明排序成功；否则图中存在环。

四、注意事项与边界情况

使用数组记录入度的前提是节点编号连续且从 0 开始。若节点是字符串或稀疏编号（如 100、200、999），需先映射为 0~n−1 再建数组，或改用 Map。另外，入度数组不保存图结构本身，仅作计数用，仍需邻接表/邻接矩阵支持遍历后继。

以上就是《Java数组实现拓扑排序入度表解析》的详细内容，更多关于的资料请关注golang学习网公众号！