0%

从课程表到拓扑排序

涉及题目包括

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

题目描述

你这个学期必须选修 numCourse 门课程,记为 0numCourse-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

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

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

      1. 当前节点所有邻接节点已被遍历,并没有发现环,则将当前节点 flag 置为−1并返回 True
  4. 若整个图 DFS 结束并未发现环,返回True

image-20210112203428586

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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[]