从课程表到拓扑排序

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 5 分钟

涉及题目包括

  • 「力扣」第 207 题：课程表（中等）；
  • 「力扣」第 210 题：课程表 II（中等）；
  • 「力扣」第 301 题：最小高度树（中等）；
  • 「力扣」第 802 题：找到最终的安全状态（中等）；
  • 「力扣」第 630 题：课程表 III（困难）；
  • 「力扣」第 329 题：矩阵中的最长递增路径（困难）；
  • 「力扣」第 1245 题：树的直径（中等）；
  • 「力扣」第 444 题：序列重建（中等）；
  • 「力扣」第 1136 题：平行课程（困难）；
  • 「力扣」第 269 题：火星词典（困难）。

题目描述

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

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

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

示例 1:

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

示例 2:

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

提示：

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

拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

该题的思路是通过拓扑排序判断该课程安排图是否是有向无环图(DAG) ：课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency，以降低算法时间复杂度。

深度遍历搜索(解答207)

原理是通过 DFS 判断图中是否有环。

  1. 使用DFS方法遍历图中的点是否形成环，

  2. 借助一个标志列表 flags，用于判断每个节点 i （课程）的状态

    1. 未被 DFS 访问：i == 0；
    2. 已被其他节点启动的 DFS 访问：i == -1；
    3. 已被当前节点启动的 DFS 访问：i == 1。

  3. 对 numCourses 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 False。DFS 流程；

    1. 终止条件：

      1. 当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 True。

      2. 当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2次访问，即课程安排图有环 ，直接返回False。

    2. 将当前访问节点 i 对应flag[i]置 1，即标记其被本轮 DFS 访问过；

    3. 递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回False；

    4. 当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为−1并返回 True。

  4. 若整个图 DFS 结束并未发现环，返回 True。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def canFinish(self, numCourses: int, prerequisites) -> bool:
        def dfs(i, adjacency, flags):
            if flags[i] == 1: return False
            if flags[i] == -1: return True
            flags[i] =  1
            for j in adjacency[i]:
                if not dfs(j, adjacency, flags): return False
            flags[i] = -1
            return True

        flags = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i, adjacency, flags): return False
        return True

广度遍历搜索(解答210)

  1. 统计课程安排图中每个节点的入度，生成 入度表 indegrees。
  2. 借助一个队列queue，将所有入度为 0的节点入队。
  3. 当queue非空时，依次将队首节点出队，在课程安排图中删除此节点pre：
    1. 并不是真正从邻接表中删除此节点pre，而是将此节点对应所有邻接节点cur的入度−1，即indegrees[cur] -= 1。
      1. 当入度 −1后邻接节点cur的入度为 0，说明cur所有的前驱节点已经被 “删除”，此时将cur入队。
  4. 在每次pre出队时，执行 numCourses--；
    1. 若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。
    2. 因此，拓扑排序出队次数等于课程个数，返回numCourses == 0判断课程是否可以成功安排。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites):
        queue = deque()
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
            indegrees[cur] += 1
        for i in range(numCourses):
            if not indegrees[i]: queue.append(i)
        res = []
        while queue:
            pre = queue.popleft()
            res.append(pre)
            numCourses -= 1
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]: queue.append(cur)
        if not numCourses: return res
        else: return[]