207. 課程表

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/course-schedule

題目

你這個(gè)學(xué)期必須選修 numCourse 門課程，記為 0 到 numCourse-1 柄错。

在選修某些課程之前需要一些先修課程嚎尤。例如，想要學(xué)習(xí)課程 0 酥泞，你需要先完成課程 1 砚殿，我們用一個(gè)匹配來表示他們：[0,1]

給定課程總量以及它們的先決條件，請你判斷是否可能完成所有課程的學(xué)習(xí)芝囤？

示例 1:

輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程似炎。學(xué)習(xí)課程 1 之前，你需要完成課程 0悯姊。所以這是可能的羡藐。

示例 2:

輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程。學(xué)習(xí)課程 1 之前悯许，你需要先完成?課程 0仆嗦；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1岸晦。這是不可能的欧啤。

提示：

輸入的先決條件是由 邊緣列表 表示的圖形，而不是 鄰接矩陣 启上。詳情請參見圖的表示法邢隧。
你可以假定輸入的先決條件中沒有重復(fù)的邊。
1 <= numCourses <= 10^5

解題思路

思路：拓?fù)渑判颍˙FS冈在，DFS）

其實(shí)倒慧，這是一道經(jīng)典的【拓?fù)渑判颉繂栴}。

首先先審題，結(jié)合示例 1 和示例 2纫谅，我們其實(shí)可以看到炫贤，其實(shí)題目問的是給定輸入先決條件表示的圖形（也就是課程表）是否是有向無環(huán)圖。也是說付秕，當(dāng)確定先決條件之后兰珍，圖形不能存在環(huán)，否則不成立询吴。

有向無環(huán)圖（DAG）：指的一個(gè)有向圖從任意頂點(diǎn)出發(fā)無法經(jīng)過若干條邊回到該點(diǎn)掠河，則該圖是一個(gè)有向無環(huán)圖。

有向無環(huán)圖猛计，詳細(xì)信息可由下方入口進(jìn)行了解
https://en.wikipedia.org/wiki/Directed_acyclic_graph （維基百科：有向無環(huán)圖）
https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE/10972513?fr=aladdin （百度百科：有向無環(huán)圖）

那么當(dāng)要求課程安排圖是否是有向無環(huán)圖時(shí)唠摹，我們用拓?fù)渑判騺砼袛唷Ｍ負(fù)渑判颍簩D所有頂點(diǎn)進(jìn)行排序成線性序列奉瘤，使得圖中任意一個(gè)有向邊 uv勾拉，u 在線性序列中出現(xiàn)在 v 前面。

拓?fù)渑判虻廖拢敿?xì)信息可由下方入口進(jìn)行了解
https://en.wikipedia.org/wiki/Topological_sorting （維基百科：拓?fù)渑判颍?br> https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin （百度百科：拓?fù)渑判颍?/p>

在題目中的提示中有說明藕赞，輸入的先決條件時(shí)由 邊緣列表 表示，在這里肌访，我們要將此轉(zhuǎn)換為 鄰接表找默。

鄰接表，詳細(xì)信息可由下方入口進(jìn)行了解
https://en.wikipedia.org/wiki/Adjacency_list （維基百科：鄰接表）
https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E8%A1%A8/9796152?fr=aladdin （百度百科：鄰接表）

廣度優(yōu)先搜索（BFS）

首先吼驶，先將邊緣列表表示的先決條件轉(zhuǎn)換得到鄰接表惩激。然后統(tǒng)計(jì)圖中每個(gè)節(jié)點(diǎn)的入度情況，存儲在一個(gè)列表中蟹演。（當(dāng)入度為 0 時(shí)风钻，表示點(diǎn)不作為任何邊的終點(diǎn)，也就說該點(diǎn)是所有連接邊的起點(diǎn)）

在這里酒请，定義輔助隊(duì)列 queue骡技，將所有入度為 0 的節(jié)點(diǎn)存入隊(duì)列中，用于后續(xù)處理羞反。

開始進(jìn)行搜索布朦，令隊(duì)列中的節(jié)點(diǎn)出隊(duì)：

將當(dāng)前節(jié)點(diǎn)鄰接節(jié)點(diǎn)入度減 1；
當(dāng)鄰接節(jié)點(diǎn)入度為 0 時(shí)昼窗，將其入隊(duì)是趴。

當(dāng)隊(duì)列中的節(jié)點(diǎn)出隊(duì)時(shí)，令課程總量減 1：

如果課程圖是有向無環(huán)圖澄惊，若完成拓?fù)渑判蛩敉荆敲此械墓?jié)點(diǎn)都會入隊(duì)出隊(duì)富雅；
若是課程圖存在環(huán)，那么一定存在節(jié)點(diǎn)入度不為 0 的情況肛搬；
也就是說没佑，當(dāng)所有節(jié)點(diǎn)入隊(duì)出隊(duì)后，課程總量為 0 的情況下温赔，也就能證明課程圖是否是有向無環(huán)圖蛤奢。

具體的代碼見【代碼實(shí)現(xiàn) # 廣度優(yōu)先搜索】

深度優(yōu)先搜索（DFS）

我們先看使用深度優(yōu)先搜索的思路來判斷圖是否有環(huán)。

在這里让腹，我們借助一個(gè)輔助列表（當(dāng)然也可以考慮用棧）標(biāo)記每個(gè)節(jié)點(diǎn)的狀態(tài)：

未標(biāo)記远剩，令此時(shí)狀態(tài)為 0；
臨時(shí)標(biāo)記骇窍，令此時(shí)狀態(tài)為 1；
永久標(biāo)記锥余，令此時(shí)狀態(tài)為 -1腹纳。

開始對每個(gè)節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索，當(dāng)存在環(huán)時(shí)驱犹，返回 False嘲恍，執(zhí)行過程如下：

當(dāng)節(jié)點(diǎn)狀態(tài)為 -1 時(shí)，表示已永久標(biāo)記雄驹，此時(shí)已搜索完畢佃牛，不許重復(fù)搜索，直接返回 True医舆；
當(dāng)節(jié)點(diǎn)狀態(tài)為 1 時(shí)俘侠，表示臨時(shí)標(biāo)記，也就說此節(jié)點(diǎn)蔬将，在此次深搜中又一次對該節(jié)點(diǎn)進(jìn)行了搜索爷速，那么表示圖中存在環(huán)，那么直接返回 False霞怀；
當(dāng)狀態(tài)為 0 時(shí)惫东，先將節(jié)點(diǎn)臨時(shí)標(biāo)記（令狀態(tài)為 1），然后以此點(diǎn)繼續(xù)搜索毙石，直至遇到終止條件廉沮。
當(dāng)節(jié)點(diǎn)搜索完畢，未發(fā)現(xiàn)閉環(huán)徐矩，則去除臨時(shí)標(biāo)記滞时，將節(jié)點(diǎn)進(jìn)行永久標(biāo)記（令狀態(tài)為 -1）

如果所有節(jié)點(diǎn)都搜索完畢后，不存在環(huán)丧蘸，則返回 True漂洋。

具體的代碼見【代碼實(shí)現(xiàn) # 深度優(yōu)先搜索】

代碼實(shí)現(xiàn)

# 廣度優(yōu)先搜索
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import deque

        # 將邊緣列表表示的先決條件轉(zhuǎn)化為 鄰接表
        adjacency = [[] for _ in range(numCourses)]
        # 定義列表統(tǒng)計(jì)圖中每個(gè)節(jié)點(diǎn)的入度情況
        indegree = [0] * numCourses

        for info in prerequisites:
            adjacency[info[1]].append(info[0])
            indegree[info[0]] += 1
        
        queue = deque()

        # 將入度為 0 的節(jié)點(diǎn)入隊(duì)
        for i in range(len(indegree)):
            if not indegree[i]:
                queue.append(i)
        # 開始進(jìn)行搜索
        while queue:
            u = queue.popleft()
            numCourses -= 1
            # 搜索鄰接節(jié)點(diǎn)
            for v in adjacency[u]:
                # 將鄰接節(jié)點(diǎn)入度減 1
                indegree[v] -= 1
                # 如果入度為 0遥皂，入隊(duì)
                if indegree[v] == 0:
                    queue.append(v)

        return numCourses == 0

# 深度優(yōu)先搜索
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(adjacency, sign, i):
            if sign[i] == -1:
                return True
            if sign[i] == 1:
                return False
            # 開始搜索，先進(jìn)行臨時(shí)標(biāo)記
            sign[i] = 1
            # 以此節(jié)點(diǎn)往下搜索
            for j in adjacency[i]:
                if not dfs(adjacency, sign, j):
                    return False
            sign[i] = -1
            return True

        # 定義輔助列表標(biāo)記狀態(tài)刽漂，初始化為 0演训，表示未標(biāo)記
        sign = [0] * numCourses
        # 將邊緣列表表示的先決條件轉(zhuǎn)化為 鄰接表
        adjacency = [[] for _ in range(numCourses)]
        for info in  prerequisites:
            adjacency[info[1]].append(info[0])
        
        # 開始深搜
        for i in range(numCourses):
            if not dfs(adjacency, sign, i):
                return False
        return True

實(shí)現(xiàn)結(jié)果

實(shí)現(xiàn)結(jié)果 | 廣度優(yōu)先搜索

實(shí)現(xiàn)結(jié)果 | 深度優(yōu)先搜索

歡迎關(guān)注

公眾號【書所集錄】

LeetCode 207. 課程表 | Python