LeetCode 上的 207. 课程表问题是一个经典的图论问题。该问题要求判断一个课程安排是否可行，即是否存在一个顺序，可以完成所有课程。

问题描述

给定一个整数数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示课程 ai 是课程 bi 的先决条件。判断是否可能完成所有课程。

示例

输入: prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: false
解释: 课程 3 是课程 1 和课程 2 的先决条件，但课程 1 和课程 2 互相没有先决条件，所以无法完成所有课程。

解题思路

  1. 构建图和入度数组：首先，根据 prerequisites 构建一个有向图，表示课程之间的依赖关系。同时，创建一个入度数组，记录每个课程的先决条件数量。
  2. 拓扑排序：使用拓扑排序算法，从入度为 0 的节点开始，逐步减少其他节点的入度，并检查是否有环存在。
  3. 判断结果：如果所有课程都能被完成，则返回 true，否则返回 false。

代码示例（Python）

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    # 构建图和入度数组
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    # 拓扑排序
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    visited = 0

    while queue:
        node = queue.popleft()
        visited += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 判断是否所有课程都被访问
    return visited == numCourses

# 示例
print(canFinish(4, [[1,0],[2,0],[3,1],[3,2]]))  # 输出: False

扩展阅读

更多关于图论和拓扑排序的内容，可以参考 图论基础。

[center]课程表问题示例