拓扑排序是对有向无环图（DAG, Directed Acyclic Graph）的一种线性排序，它使得对于每一条从顶点u到顶点v的有向边u -> v，在最终的排序中u总是在v之前。这种排序常用于安排任务或活动的顺序，其中某些任务必须在其他任务开始之前完成。

基本步骤

1. 初始化：计算所有节点的入度（指向该节点的边的数量），并将所有入度为0的节点加入队列。
2. 处理节点：从队列中取出一个节点，将其输出，并且对于每一个由该节点出发的边，减少目标节点的入度。如果某个目标节点的入度变为0，则将该节点也加入队列。
3. 重复处理：重复上述过程直到队列为空。
4. 检查结果：如果最后输出的节点数等于图中的节点总数，说明拓扑排序成功；否则，说明图中有环，无法进行拓扑排序。

Java实现

下面是一个使用Java实现的拓扑排序算法，基于邻接表和队列：

查看代码

public class TopologicalSort {
    public static List<Integer> topologicalSort(int num, int[][] arr) {
        // 第一步，建立邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            graph.add(new ArrayList<>());
        }

        // 第二步，建立一个结点入度的数组
        int[] indegree = new int[num];

        // 第三步，将数据存入邻接表，并将所有结点入度存入数组
        for (int[] edge : arr) {
            int from = edge[0];
            int to = edge[1];
            graph.get(from).add(to);  // 添加有向边 from -> to
            indegree[to]++;  // 增加目标节点的入度
        }

        // 第四步，将入度为0的点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < num; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 第五步，若结点入度为0就出队列
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);  // 输出当前节点
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);  // 如果邻居节点入度为0，加入队列
                }
            }
        }

        // 最后如果输出的节点数==总结点数，说明无环
        return result.size() == num ? result : new ArrayList<>();
    }
}

解释代码：

• 邻接表构建：我们使用List<List<Integer>>来表示邻接表。每个列表元素代表一个节点，列表内的元素是该节点指向的所有节点。
• 入度数组：int[] indegree用来记录每个节点的入度。
• 队列：使用Queue<Integer>来存储入度为0的节点。
• 主循环：不断从队列中取出节点，输出，并更新其相邻节点的入度。如果相邻节点的入度减至0，则将它们加入队列。
• 返回结果：如果最终结果列表的大小与节点数量相同，说明没有环，可以得到有效的拓扑排序；否则，说明存在环，无法进行拓扑排序。