[LC]207. 课程表 I

🚩传送门：力扣题目

题目

你这个学期必须选修 门课程，记为 到 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 给出，其中 ，表示如果要学习课程 则 必须 先学习课程 。例如，先修课程对表示：想要学习课程 ，你需要先完成课程 。

请你判断是否可能完成所有课程的学习 ？如果可以，返回 true；否则，返回 false。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

解题思路：拓扑排序

拓扑排序可以深搜（DFS）也可以广搜（BFS）

本题是一道经典的「拓扑排序」问题，给定一个包含 个节点的有向图 ，我们给出它的节点编号的一种排列。
如果满足：对于图中的任意一条有向边， 在排列中都出现在 的前面。那么称该排列是图 的「拓扑排序」。

根据上述的 定义，我们可以得出两个结论：

• 如果图中存在环（即图不是「有向无环图」），那么图不存在拓扑排序。

  这是因为假设图中存在环 ，那么 在排列中必须出现在 的前面，但 同时也必须出现在 的前面，因此无法满足这个要求

• 如果图是有向无环图，那么它的拓扑排序可能不止一种。

  举一个最极端的例子，如果图值包含 个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。

广度搜索

复杂度分析

时间复杂度：，遍历一个图需要访问所有节点和所有临边， 和 分别为节点数量和临边数量；

空间复杂度：，为建立邻接表所需额外空间， 长度为 ，并存储 条临边的数据。

我的代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 入度数组
        int[] indegrees = new int[numCourses];
        // 存储边信息
        List<List<Integer>> edges = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
            edges.add(new ArrayList<>());
        // 获得每门课程的入度和边。
        for(int[] cp : prerequisites) {
            indegrees[cp[0]]++;                // 入度自增
            edges.get(cp[1]).add(cp[0]);    // 添加由自身u出发到v的边
        }
        // 获得入度为0的所有课程入队列
        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) queue.add(i);
        // BFS 搜索
        while(!queue.isEmpty()) {
            int u = queue.poll();
            numCourses--;
            for(int v : edges.get(u))
                if(--indegrees[v] == 0) queue.add(v);
        }
        return numCourses == 0;
    }
}

深度优先搜索

复杂度分析

时间复杂度：，遍历一个图需要访问所有节点和所有临边， 和 分别为节点数量和临边数量；

空间复杂度：，为建立邻接表所需额外空间， 长度为 ，并存储 条临边的数据。

我的代码

class Solution {
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges=new ArrayList<List<Integer>>();
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        // 添加边的信息
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        // 遍历每一个结点做起始结点开始dfs
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }
    public void dfs(int u) {
        // 正在访问
        visited[u] = 1;
        // 一条由点 u -> v 的边 
        for (int v: edges.get(u)) {
            // 未访问
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // 遇到一条正在访问的边,说明有环,刚才遍历过它
                valid = false;
                return;
            }
        }
        // 完成访问
        visited[u] = 2;
    }
}