[leetcode]第三十三部分(210)

210-Course Schedule II

问题描述

我们一共需要上n门课, 标识为0n-1.

一些课程可能有一些前置条件, 例如: 如果想要上课程0的话, 我们得先上课程1, 使用表达式表示为 [0, 1].

给定总课程数以及一个前置 的列表, 返回我们想要完成所有课程的顺序.

可能有多个正确的顺序, 我们只需要返回其中的一个即可. 如果无法完成所有的课程, 返回一个空数组.

示例1

Input: 2, [[1,0]] 
Output: [0,1]
解释: 一共需要上两门课程, 如果要上课程1, 需要先完成课程0, 因此, 正确的课程顺序为: [0,1].

示例2

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
解释: 一共需要上四门课程, 如果需要上课程3, 需要先完成课程1和课程2. 而课程1和2都需要在完成课程0之后才能完成. 因此一个正确的顺序是: [0,1,2,3]. 另一个正确的顺序是: [0,2,1,3] .

注意:
– 输入的前置条件表示为 边的列表 的图, 而不是邻接矩阵.
– 可以假设在输入前置中没有重复的边.

解题思路

这是在大学期间大家都可能会面临到的非常常见的问题. 我们可能想上一系列感兴趣的课程. 然而, 总所周知, 大多数课程都有大量与之相关的前置条件. 一些课程有严格的要求, 但是其它课程可能只有一些 推荐 的前置课程. 然而, 为了有全面的学习体验, 我们应该要遵循推荐的前置课程集合. 那么, 一个人如何决定课程的顺序以避免错过任何课程呢?

正如题目中提到的, 这个问题对于基于图的算法来说是非常契合的, 在这里, 非常容易能够将问题中的元素建模为一个图. 首先, 我们来看一下问题和元素的图形表示, 然后再介绍解题思路.

我们可以将问题中提供的信息表示为图的格式:

  • G(V,E)表示一个有向的/无权重的
  • 每门课程都表示为图中的节点
  • 课程之间的前置条件关系表示为边, 因此, 给定一个数组对: 问题中的[a, b] 表示课程b为课程a的前置课程. 在图中, 可以表示为有向边: b ➔ a
  • 图是一个循环图, 因为图中可能有环. 如果图示无环的, 那么问题中要求的课程顺序经常 就是可能的. 而上面提到的可能出现不存在的课程顺序, 这就意味着我们可能有循环图

下面我们来看看表示一系列课程的示例图: 其中一个为存在可能的顺序, 而另一个为没有合适的顺序. 一旦看到这两个示例图, 我们非常容易解释解题方案.

正如上图展示的, 可能的课程顺序之一: C6 ➔ C4 ➔ C1 ➔ C5 ➔ C2 ➔ C3, 另一个可能的课程顺序为: C6 ➔ C4 ➔ C5 ➔ C1 ➔ C2 ➔ C3. 下面再看看没有可能顺序的课程图:


注意: 第一张图中变化的边已经改为了红色.

很明显, 图中环中的存在就说明不可能存在合适的前置顺序. 举个例子, 在课程S1和课程S2互为前置课程的情况下不可能有合适的顺序. 相似的理论也适用于上图中展示的更大的圈.

这种课程的排序其实是一个图领域中一个非常常用的算法问题 — 拓扑排序顺序. 接下来将会介绍解决这个问题的深度优先算法.

方法: 深度优先

假设在深度优先的遍历过程中, 有一个节点A:

深度优先方法的工作方式是: 首先, 考虑从A开始的所有的所有路径, 在遍历结束之后, 移动到其它节点. 从节点A中开始的路径中的所有节点都会将A当作祖先节点. 这个方法与问题契合的点在于: 从课程A中发起的路径中的所有课程都会把A作为前置课程.

现在, 我们知道如何获得有特殊课程作为前置课程的所有课程. 如果有可能的课程顺序, 那么课程A应该在所有其它以它为前置课程的之前. 解决这个问题的思路可以使用深度优先搜索, 我们先来看看常规的伪代码:

S=课程的栈
function dfs(node)
    for each neighbor in adjacency list of node
        dfs(neighbor)
    add node to S

代码

from collections import defaultdict
class Solution:

    WHITE = 1
    GRAY = 2
    BLACK = 3

    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        # Create the adjacency list representation of the graph
        adj_list = defaultdict(list)

        # A pair [a, b] in the input represents edge from b --> a
        for dest, src in prerequisites:
            adj_list[src].append(dest)

        topological_sorted_order = []
        is_possible = True

        # By default all vertces are WHITE
        color = {k: Solution.WHITE for k in range(numCourses)}
        def dfs(node):
            nonlocal is_possible

            # Don't recurse further if we found a cycle already
            if not is_possible:
                return

            # Start the recursion
            color[node] = Solution.GRAY

            # Traverse on neighboring vertices
            if node in adj_list:
                for neighbor in adj_list[node]:
                    if color[neighbor] == Solution.WHITE:
                        dfs(neighbor)
                    elif color[neighbor] == Solution.GRAY:
                         # An edge to a GRAY vertex represents a cycle
                        is_possible = False

            # Recursion ends. We mark it as black
            color[node] = Solution.BLACK
            topological_sorted_order.append(node)

        for vertex in range(numCourses):
            # If the node is unprocessed, then call dfs on it.
            if color[vertex] == Solution.WHITE:
                dfs(vertex)

        return topological_sorted_order[::-1] if is_possible else []
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注