拓扑排序理论基础

拓扑排序算法是将 有向无环图 进行 线性排序 的 算法。

学习重点是 BFS

拓扑排序中，如何找到出发节点：优先找 入度为 0 的节点，只有入读为0，它才是出发节点。

拓扑排序的过程一共两步：

第一步：找到入度为9的节点，加入结果集

第二步：将该节点从图中移除

循环以上两步，直到 所有点 都在图中被移除了

结果集的顺序，就是我们想要拓扑排序的顺序。

如果有 有向环 怎么办？

经过拓扑排序两步操作完，发现结果集元素个数 不等于 图中节点个数，我们就可以断定 图中 一定有 有向环。这也是拓扑排序判断 有向环 的方法。

117.软件构建

构建图grid，记录节点之间的连接关系（即有向图）使用 链接表

链接表实现
List<List<Integer>> grid = new ArrayList<>(n);

记录每个节点的入度

int[] inDegree = new int[n];//本题的n个文件，文件编号是从0到n-1，所有从0开始记录正常遍历就可以，所以设置数组大小为n即可。之前设置n+1是因为那些题节点都从1开始，所以为了看起来一致，就设置n+1大小，从下标1开始记录。

初始化 图 和 入度数组
for(int i = 0; i < n; i++){
    grid.add(new ArrayList<>());
}
for(int i = 0; i < m; i++){
    int s = scanner.nextInt();
    int t = scanner.nextInt();
    grid.get(s).add(t); //节点s 指向 t
    inDegree[t]++; //t的入度加一
}

遍历所有节点，将入度为0的节点放入队列中（因为不一定只有一个入度为0的节点），所以要将这些入度为0的节点都放到队列中，依次去处理。

再遍历队列中的节点，先移除再加入结果集合。

如何实现移除效果？不单是要再队列中移除，还要体现在grid中，移除的目的是将该节点的所有连接的点的入度都减去1。

完整可运行代码：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //记录图
        List<List<Integer>> grid = new ArrayList<>();
        //记录每个节点入度
        int[] inDegree = new int[n];
        //初始化
        for(int i = 0; i < n; i++){
            grid.add(new ArrayList<>());
        }
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            grid.get(s).add(t);
            inDegree[t]++;
        }
        //队列 存储所有入度为0的节点
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(inDegree[i] == 0){
                q.add(i);
            }
        }
        List<Integer> result = new ArrayList<>();
        while(!q.isEmpty()){
            int node = q.poll();
            result.add(node);
            //找到该节点的所有连接节点，将这些节点的入度都减一
            for(int nd : grid.get(node)){
                inDegree[nd]--;
                if(inDegree[nd] == 0){
                    q.add(nd);
                }
            }
        }
        //打印结果result
        if(result.size() == n){//说明没有有向环，有向环也要输出-1
            for(int i = 0; i < result.size() - 1; i++){
                System.out.print(result.get(i) + " ");
            }
            System.out.print(result.get(result.size()-1));
        }else{
            System.out.print(-1);
        }  
    }
}