LeetCode-207. 课程表_leetcode 207 课程表

-.- 这题不会做，记录下大佬的题解（难度：中等）

一、题目内容

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

在选修某些课程之前需要一些先修课程。 例如，想要学习课程0 ，你需要先完成课程 1，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:

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

提示：

输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5

二、题解过程

1、解题思路

1. 本题可约化为： 课程安排图是否是有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
2. 思路是通过 拓扑排序 判断此课程安排图是否是 有向无环图(DAG) 。 拓扑排序原理： 对 DAG 的顶点进行排序，使得对每一条有向边(u, v)(u,v)，均有 uu（在排序记录中）比 vv先出现。亦可理解为对某点 vv而言，只有当 vv的所有源点均出现了，vv才能出现。
3. 通过课程前置条件列表 prerequisites可以得到课程安排图的 邻接表 adjacency，以降低算法时间复杂度，以下两种方法都会用到邻接表。

2、图算法简单讲解

2.1图的各种存储结构及实现

1.邻接矩阵：
  (1)总体思路
  邻接矩阵是用两个数组来表示一个图：一个一维数组用来存储每个顶点的信息；一个二维数组（即邻接矩阵）用来存储图中的边或弧信息。对于图G =(V, E)来说，邻接矩阵matrix是一个|V|*|V|的方阵，假设1 <= i, j <= |V|，如果matrix[i][j] == 0，则表示顶点i和顶点j之间没有边相连；反之，如果matrix[i][j] != 0，则表示表示顶点i和顶点j之间有边相连，且matrix[i][j]存储的值即为该边的权重。
  (2) 数据结构
  首先明确，一个图结构中包含两个数组，一个顶点表和一个用来存储图中边或弧信息的二维数组；

顶点表：用来存储图中顶点信息，是一个一维数组，顶点信息可以自定义，此处定义为int类型：

邻接矩阵：一个二维矩阵，大小为|V|*|V|，用来存储图中边或弧信息，其中二维矩阵的类型（即边的权值类型）可以自定义，此处定义为int：
2.邻接链表
  (1)总体思路
  邻接链表是一种不错的图存储结构，由于它在表示稀疏图的时候非常紧凑而成为通常的选择。对于图G =(V, E)来说，在其邻接链表表示中，每个结点对应一条链表，因此这个图里有V条链表。假设用一个V维的数组Adj来存储这V条链表，且Adj[i]表示的是结点i对应的链表，那么Adj[i]这条链表里存储的就是所有与节点i之间有边相连的结点，即与结点i相邻的结点。举个例子：
在这里插入图片描述:
        

  上图中的(a)是一个无向图，(b)是它的邻接链表表示，可以看到图中有5个结点，每个结点对应一条链表，链表中的结点都是与该节点相邻的，例如结点1的链表中有结点2和结点5，它们都与结点1相邻。

  (2)数据结构
  首先要明确，一个图包含了一个顶点表，而顶点表里的每一项又包含一个边表；

  顶点表：该表包含了图里的所有顶点，顶点表的每一项用于存储该顶点的属性（例如该结点对应的值），以及指向其边表的第一个结点的指针。
  边表：某个顶点的边表存放了与其相邻的结点。

3、算法简介

1）广度优先遍历（BFS）
简单来说从初始点出发，一层一层从内而外的遍历方式，就叫做广度优先遍历，本质上与二叉树的层序遍历差不多。

实现广度优先遍历的关键在于[重放]，即是把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放。要实现重放也需要利用额外的存储空间，可以利用队列的先入先出特性来实现。

那么无论是哪种遍历方法，当我获取一个顶点的若干邻近顶点时，如果判断这些顶点哪个已经被访问过，哪个没有被访问过？
我们可以利用一个布尔类型的数组来存储所有顶点的遍历状态，顶点对应数组元素的初始值都是false，代表未遍历，遍历之后变为true。

参考链接：https://blog.csdn.net/weixin_30722589/article/details/97363179.

2）深度优先遍历（DFS）
简单的来说就是先深入探索，走到头再回退寻找其他出路的遍历方式，就叫做深度优先遍历。本质上与二叉树的前序、中序、后序遍历差不多。

实现深度优先遍历的关键在于[回溯]，即是自后向前的追溯曾经访问过的路径。要想实现回溯，可以利用栈的先入后出特性，也可以利用递归的方式（因为递归本身就是基于调用栈来实现的）。

那么无论是哪种遍历方法，当我获取一个顶点的若干邻近顶点时，如果判断这些顶点哪个已经被访问过，哪个没有被访问过？
我们可以利用一个布尔类型的数组来存储所有顶点的遍历状态，顶点对应数组元素的初始值都是false，代表未遍历，遍历之后变为true

参考链接：https://blog.csdn.net/weixin_30722589/article/details/97363179.

4、解法

解法一（广度优先遍历）：

算法流程

1. 统计课程安排图中每个节点的入度，生成入度表 indegrees。
2. 借助一个队列queue，将所有入度为0的节点入列。
3. 当queue非空时，依次将队首节点出队，在课程安排图中删除此节点pre：
   1）并不是真正从邻接表中删除节点pre，而是将此节点对应所有邻接节点cur的入度减一，
   2）当入度减一后邻接节点cur的入度为0，说明cur所有的前驱节点已经被“删除”，此时将cur入队。
4. 在每次pre出队时，执行numCourses–；
   1）若整个课程安排图是有向无环图，则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点入度始终不为0；
   2）因此，拓扑排序出队次数等于课程个数，返回numCourses == 0 判断课程是否可以安排成功。

class Solution2 {
    List<List<Integer>> edges;
    int[] indegrees;
    Queue<Integer> queue;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        indegrees = new int[numCourses];
        queue = new LinkedList<>();
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        //图的链接表的初始化与图中每个节点的入度表的初始化
        for (int i = 0; i < prerequisites.length; i++) {
            indegrees[prerequisites[i][0]]++;
            edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int tem = queue.poll();
            numCourses--;
            ArrayList<Integer> list = (ArrayList<Integer>) edges.get(tem);
            for (int i = 0; i < list.size(); i++) {
                if(--indegrees[list.get(i)] == 0) {
                    queue.offer(list.get(i));
                }
            }
        }
        return numCourses == 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

复杂度分析：
时间复杂度 O(N + M)O(N+M)： 遍历一个图需要访问所有节点和所有临边，NN 和 MM 分别为节点数量和临边数量；
空间复杂度 O(N + M)O(N+M)： 为建立邻接表所需额外空间，adjacency 长度为 NN ，并存储 MM 条临边的数据。

解法二（深度优先遍历）

算法流程

1. 借助一个标志列表flags，用来判断每个节点 i(课程) 的状态
   1.未被DFS访问：i == 0;
   2.已被其他节点启动的DFS访问：i == -1；
   3.已经被当前节点启动的DFS访问：i == 1;
2. 对numCourses个节点依次执行DFS，判断每个节点起步DFS是否存在环，若存在环直接返回False。DFS流程：
   1.终止条件：当 flag[i] == -1，说明当前访问节点已经被其他节点启动的DFS访问，无需再重复搜索，直接返回ture；当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2 次访问，即 课程安排图有环 ，直接返回 False。
   2.将当前访问节点 i 对应 flag[i] 置 1，即标记其被本轮DFS访问过；
   3.递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回 false；
   4.当前节点所有邻接点已经被遍历，并没有发现环，则将当前节点 flag 置为 -1 并返回 True。
3. 若整个图DFS结束并没有发现环，返回True。

class Solution {
    List<List<Integer>> edges;
    int[] flags;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        flags= new int[numCourses];
        edges = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        //图的链接表的初始化
        for (int i = 0; i < prerequisites.length; i++) {
            edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        
		for(int i = 0; i < numCourses; i++)
            if(!dfs(edges, flags, i)) return false;
        return true;
	}
	private boolean dfs(List<List<Integer>> edges,int[] flags,int i) {
		if (flags[i] == 1) {
			return false;
		}
		if (flags[i] == -1) {
			return true;
		}
		 flags[i] = 1;
        for(Integer j : edges.get(i))
            if(!dfs(edges, flags, j)) return false;
        flags[i] = -1;
        return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34