1. 拓扑排序

1.1 场景

对有向无环图（DGA），顶点经过排序后得到一个顶点序列。 对任意节点u、v，若图中存在u --> v的边，则排序后顶点u也应在v前面

1.2 思路

从DGA图中找到一个没有前驱的顶点，输出 删除以这个点为起点的边 重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！

（a）a没有前驱节点（入度为0） （b）输出a，删除以a为起点的边（b、c、d入度减1） （c）f、c没有前驱节点，选取c输出，删除以c为起点的边（b、e入度减1） （d）f、b没有前驱节点，输出b，删除以b为起点的边 （e）f没有前驱节点，输出f，删除以f为起点的边（d、e入度减1） （f）d没有前驱节点，输出d，删除以d为起点的边（e入度减1） （g）只剩最后一个节点e，输出e

1.3 代码

class TopologicalSort {
          
   

    public List<Integer> topologicalSort(int n, int[][] adjacencyList) {
          
   
        List<Integer> topoRes = new ArrayList<>();
        int[] inDegree = new int[n]; // 保存所有节点的入度
        for (int[] parent : adjacencyList) {
          
   
            for (int child : parent) {
          
   
                inDegree[child]++; // 每有一个父节点，入度+1
            }
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
          
   
            if (inDegree[i] == 0) deque.offer(i); // 找入度为0的节点
        }
        
        while (!deque.isEmpty()) {
          
    // bfs
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
          
   
                inDegree[child]--; // 将以curr为前驱节点的节点的入度-1
                if (inDegree[child] == 0) {
          
   
                    deque.offer(child);
                }
            }
        }
    
        return topoRes.size() == n ? topoRes : new ArrayList<>(); // 是否存在环
    }
}