Day 77 图论：有向图环检测，拓扑排序, 课程表 I II

207. Course Schedule

• 思路
  • example
  • 有向图

graph[from] = to, 先修from才能修to

• 关键：是否存在环

无法修完所有课程: 存在循环依赖

• 避免重复访问节点：用visited数组
• 判断当前路径中是否有环：用path数组 (回溯）

选择撤销操作在循环外
类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景。

• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def traversal(graph, i):
            if onPath[i]: # 找到环
                return False 
            if visited[i]:
                return True
            visited[i] = True 
            onPath[i] = True 
            for j in graph[i]:
                if traversal(graph, j) == False:
                    return False 
            onPath[i] = False # 回溯
            return True  
        graph = collections.defaultdict(list)
        for pair in prerequisites:
            graph[pair[1]].append(pair[0]) # graph[from] = to
        visited = [False for _ in range(numCourses)]
        onPath = [False for _ in range(numCourses)] # 当前路径
        for i in range(numCourses):
            if traversal(graph, i) == False: # 有环
                return False 
        return True 

• 进阶：返回这个环具体有哪些节点

  
  

TBA

210. Course Schedule II

• 思路
  • example
  • 有向图
  • BFS
  • 入度
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        inDeg = [0 for _ in range(numCourses)]
        for pair in prerequisites:
            graph[pair[1]].append(pair[0]) # graph[from] = to
            inDeg[pair[0]] += 1
        que = collections.deque()
        for i in range(numCourses):
            if inDeg[i] == 0:
                que.append(i)
        res = []
        while que:
            i = que.popleft() # 待加进结果列表的课程
            res.append(i) # 必有inDeg[i] == 0
            for j in graph[i]:
                inDeg[j] -= 1
                if inDeg[j] == 0: # 课程j没有先决课程了，可以准备加进结果列表
                    que.append(j)
        if len(res) == numCourses:
            return res 
        else:
            return []

[图的遍历]一般需要 visited 数组防止走回头路，这里的 BFS 算法其实是通过 indegree 数组实现的 visited 数组的作用，只有入度为 0 的节点才能入队，从而保证不会出现死循环。