题目：

207. 课程表
在这里插入图片描述

题解：拓扑排序 + 广度优先搜索

在这里插入图片描述

1. 无向图及其邻接表：

2. 有向图及其邻接表：

1. 解释一：

在这里插入图片描述

2. 解释二：

在这里插入图片描述

代码：拓扑排序 + 广度优先搜索

import java.util.*;
public class code207 { 
    // 边缘列表 prerequisites 【后置结点，前置结点】
    public static boolean canFinish(int numCourses, int[][] prerequisites) { 
        int inDegree[] = new int[numCourses]; // 入度表,标记每个结点的入度
        //1、构建邻接表
        List<List<Integer>> adj = new ArrayList<>(); // 课程安排图的 邻接表
        for(int i = 0; i < numCourses; i++)
        { 
            List<Integer> temp = new ArrayList<>();
            adj.add(temp); // 初始化入度以及邻接表
        }
        // 2、填写邻接表与入度表,获取每个课程的入度和邻接关系
        for(int p[]: prerequisites) // 课程前置条件列表 prerequisites
        { 
            inDegree[p[0]]++; //填充入度,统计数组的每一行的开头第一个数字，在入度表里找到这个数字的下标 + 1
            adj.get(p[1]).add(p[0]); //填充邻接表,有向图的邻接表为俩个数[start，end]，这里取下标为start
        }
        // System.out.println(adj.toString());
        Queue<Integer> queue = new LinkedList<>();
        // 3、将所有入度为0的结点加入队列(加入队列的是结点的下标)
        for(int i = 0; i < numCourses; i++)
        { 
            if(inDegree[i] == 0)
            { 
                queue.add(i);
            }
        }
        // 记录已经出队的课程数量
        int cnt = 0;
        // 4、类似广度优先遍历的写法
        while(!queue.isEmpty()) // 只要队列非空
        { 
            int top = queue.poll(); // 从队首取出入度为 0 的结点
            cnt += 1;
            // 遍历当前出队结点的所有后继结点，将它们的入度减 1
            for(int cur: adj.get(top))
            { 
                inDegree[cur]--; // 将这个结点的所有邻接结点（它指向的结点）的入度减 1
                if(inDegree[cur] == 0)
                { 
                    queue.add(cur); // 在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。
                }
            }
        }
        // 当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。
        return cnt == numCourses;
    }
    public static void main(String[] args) { 
        int numCourses = 6;
        int prerequisites[][] = {  {  3, 0 }, {  3, 1 }, {  4, 1 }, {  4, 2 }, {  5, 3 }, {  5, 4 } };
        boolean res = canFinish(numCourses, prerequisites);
        System.out.println(res);
    }
}