leetcode5-17每日一题：课程表 II

由于我暂时对图论方面的知识不够熟悉，所以这个题目我并不知道如何使用BFS和DFS两种方法去实现，通过遍历来做在python的龟速加持下，超出了时间限制，因此今天的重点是对知识点进行熟悉，同时争取看懂并理解代码及背后的算法意义。

BFS和DFS两种方法

虽然之前有看过一点数据结构的知识，但是很遗憾，看到最后还有一点图论的内容就没有继续看了，因此今天看到这个题目的时候是懵逼的，并不知道要通过构建图的方法来实现，脑子里有的只有遍历，图也不知道要咋用。
不废话了，先来熟悉一下BFS和DFS两种算法。

BFS：广度优先搜索

为了方便，我就直接把我的python手写笔记贴上来，字很丑，但还算将就能看

广度优先搜索示意图

算法流程：
①随机选择一个起始点，标记为待搜索状态；
②若这个点有未标记邻接结点，将该点标记为搜索完成状态，并将其所有邻接结点标记为待搜索状态，对所有标记为待搜索状态的结点递归进行搜索；若这个点无未标记邻接结点，这将该点标记为搜索完成状态，并回到①；
③当所有点均为搜索完成状态，搜索结束。

DFS：深度优先搜索

深度优先搜索示意图

算法流程
①随机选择一个起始点，标记为待搜索状态；
②若该点有未搜索邻接结点，将其中一个邻接结点标记为待搜索状态，并将这个邻接结点重复步骤②进行迭代；若该点无未搜索邻接结点，将该点标记为搜索完成状态，并返回指向其递归过来的结点重复步骤②进行迭代；
③若①中选择的起始点已被标记为搜索完成状态，则重新选取一个未被标记的点作为起始点，并重复步骤①；
④当所有点均为搜索完成状态，搜索结束。

关于BFS和DFS的参考，我是参考如下链接的：
链接1

这时候看回题目：

题目

有了算法基础，就可以进行这道题的解答了。因为有先修后修的关系存在，因此这题可以通过构造图来进行解答。

补充一个知识点：defaultdict
简单地说，就是由于python自带的字典不能为不存在于字典中的key提供默认值，因此需要collections中的defaultdict函数来为不存在的key提供一个默认值，这样就可以在没有key的情况下也能进行查询并返回设定的默认值。
参考链接
再补充一个概念：
①入度：有向图中某点作为图中变得终点的数量之和

代码源于leetcode官方解答，作者为LeetCode-Solution。现在还写不出来，只能先参考一下答案学习一下了
BFS代码如下：

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 存储有向图
        edges = collections.defaultdict(list)
        # 存储每个节点的入度
        indeg = [0] * numCourses
        # 存储答案
        result = list()

        for info in prerequisites:
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1
        
        # 将所有入度为 0 的节点放入队列中
        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])

        while q:
            # 从队首取出一个节点
            u = q.popleft()
            # 放入答案中
            result.append(u)
            for v in edges[u]:
                indeg[v] -= 1
                # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if indeg[v] == 0:
                    q.append(v)

        if len(result) != numCourses:
            result = list()
        return result

BFS的实现原理如下：
首先记录所有课程的入度，不需要先修课程的课程入度为0，其余课程有几个先修课程入度就为几。将所有入度为0的课程加入到输出列表中，在图中删除这些课程，并将所有结点的入度减1，然后重复课程的入度判断，知道所有课程被加入到输出列表为止。
DFS代码如下：

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 存储有向图
        edges = collections.defaultdict(list)
        # 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
        visited = [0] * numCourses
        # 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶
        result = list()
        # 判断有向图中是否有环
        invalid = False

        for info in prerequisites:
            edges[info[1]].append(info[0])
        
        def dfs(u: int):
            nonlocal invalid
            # 将节点标记为「搜索中」
            visited[u] = 1
            # 搜索其相邻节点
            # 只要发现有环，立刻停止搜索
            for v in edges[u]:
                # 如果「未搜索」那么搜索相邻节点
                if visited[v] == 0:
                    dfs(v)
                    if invalid:
                        return
                # 如果「搜索中」说明找到了环
                elif visited[v] == 1:
                    invalid = True
                    return
            # 将节点标记为「已完成」
            visited[u] = 2
            # 将节点入栈
            result.append(u)
        
        # 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for i in range(numCourses):
            if not invalid and not visited[i]:
                dfs(i)
        
        if invalid:
            return list()
        
        # 如果没有环，那么就有拓扑排序
        # 注意下标 0 为栈底，因此需要将数组反序输出
        return result[::-1]

DFS原理如下：
随机选取一个课程作为起始点，以深度优先搜索进行遍历，直到找到没有临近结点的课程，便将这个课程压入栈，并返回到其前置课程进行判定，看是否还有后置课程，如果有就继续遍历，没有则将课程压入栈，并递归地返回到前置课程，直到返回到最开始的起始点。然后随机找到别的未入栈的点，重复上述过程，直到所有课程被压入栈。然后让所有课程出栈得到最后结果。

写得不好，如果大家有发现什么问题的话烦请大家指出，谢谢！