Java实现拓扑排序算法的示例代码

下面将详细讲解Java实现拓扑排序算法的示例代码的完整攻略。

什么是拓扑排序？

拓扑排序是一种常用的有向无环图(DAG)的排序算法。拓扑排序的思想是将DAG中的节点按照拓扑关系排成一个序列，使得对于任何一个节点，它的前驱节点都排在它的前面。

拓扑排序算法实现

拓扑排序算法实现的主要步骤如下：

1. 构建图的邻接表；
2. 统计每个节点的入度；
3. 将入度为0的节点入队；
4. 不断从队首取出节点并把它的出边的终点的入度减1，若发现节点的入度为0则加入队列；
5. 直到队列为空，如果处理的节点数不足图中的节点数则说明图中有环。

下面给出Java实现的示例代码：

import java.util.*;

public class TopologicalSort {
    public List<Integer> topoSort(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();

        // 构建图的邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            graph.get(e[1]).add(e[0]);
        }

        // 统计每个节点的入度
        int[] indegree = new int[n];
        for (int[] e : edges) {
            indegree[e[0]]++;
        }

        // 将入度为0的节点入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 不断从队首取出节点并把它的出边的终点的入度减1，
        // 若发现节点的入度为0则加入队列
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res.add(u);
            for (int v : graph.get(u)) {
                if (--indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 如果处理的节点数不足图中的节点数则说明图中有环
        if (res.size() < n) {
            return new ArrayList<>();
        }

        return res;
    }
}

示例说明：

1. 构建图的邻接表：在上述示例中，我们使用了一个长度为n+1的List来保存图的邻接表，其中下标从0到n的位置分别表示0到n号节点，List的每个位置表示该节点的出边的终点。
2. 统计每个节点的入度：在上述示例中，通过遍历每一条边来统计节点的入度。
3. 将入度为0的节点入队：在上述示例中，我们使用了一个Queue来保存所有入度为0的节点。
4. 不断从队首取出节点并把它的出边的终点的入度减1：在上述示例中，我们通过遍历队首节点的所有出边，并减少它们的终点节点的入度，如果某个节点的入度为0，则将该节点加入队列。
5. 如果处理的节点数不足图中的节点数则说明图中有环：最后检查返回的结果数组的长度是否为节点数n，如果不是则说明图中存在环路。