知識點(diǎn)總結(jié)
拓?fù)渑判虿⒎且环N排序算法芦瘾，它能得到一個(gè) AOV 網(wǎng)絡(luò)的拓?fù)湫蛄校糜谂袛?strong>有向無環(huán)圖中是否有環(huán)集畅，即可以判斷一系列活動(dòng)是否有循環(huán)依賴近弟；
解決一個(gè)工程中的任務(wù)是否能夠順利完成，判斷是否出現(xiàn)環(huán)挺智。（補(bǔ)充：還有一種判斷圖中是否有環(huán)的數(shù)據(jù)結(jié)構(gòu)是“并查集”）祷愉。
具體例子：去店里吃飯的問題：顧客要求先吃飯?jiān)俑跺X，商家要求先收錢再做菜赦颇，這就是循環(huán)依賴二鳄，拓?fù)渑判蚓涂梢詭椭覀兣袛嗍欠裥纬森h(huán)。算法4那本書里面就有拓?fù)渑判颉?/p>
步驟：找無前驅(qū)的結(jié)點(diǎn)（即入度為 的結(jié)點(diǎn)）媒怯，一個(gè)一個(gè)地刪去（使用隊(duì)列或者棧）订讼，刪的時(shí)候，把鄰居結(jié)點(diǎn)的入度（即度 -1 ）扇苞。借助隊(duì)列實(shí)現(xiàn)欺殿。
“拓?fù)渑判颉庇糜趯τ邢群箜樞虻娜蝿?wù)的輸出寄纵，如果先后順序形成一個(gè)環(huán)，那么就表示這些任務(wù)頭尾依賴脖苏，就永遠(yuǎn)不能完成程拭。
因此“拓?fù)渑判颉边€可以用于檢測一個(gè)圖中是否有環(huán)。
LeetCode 上拓?fù)渑判蚰壳埃ń刂?2019 年 2 月 16 日早）一共有 5 題棍潘。
我們就做兩題恃鞋。
LeetCode 第 207 題：課程表
傳送門：207. 課程表。
現(xiàn)在你總共有 n 門課需要選蜒谤，記為
0到n-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ù)的邊宝磨。
提示:
- 這個(gè)問題相當(dāng)于查找一個(gè)循環(huán)是否存在于有向圖中弧关。如果存在循環(huán)，則不存在拓?fù)渑判蚧斤保虼瞬豢赡苓x取所有課程進(jìn)行學(xué)習(xí)世囊。
- 通過 DFS 進(jìn)行拓?fù)渑判?/a> - 一個(gè)關(guān)于Coursera的精彩視頻教程（21分鐘），介紹拓?fù)渑判虻幕靖拍睢?/li>
- 拓?fù)渑判蛞部梢酝ㄟ^ BFS 完成窿祥。
思路1：Kahn 算法茸习，即拓?fù)渑判颉?gòu)建的鄰接表就是我們通常認(rèn)識的鄰接表壁肋，每一個(gè)結(jié)點(diǎn)存放的是后繼結(jié)點(diǎn)的集合号胚。
該方法的每一步總是輸出當(dāng)前無前趨（即入度為零）的頂點(diǎn)。為避免每次選入度為 的頂點(diǎn)時(shí)掃描整個(gè)存儲空間浸遗，可設(shè)置一個(gè)隊(duì)列暫存所有入度為
的頂點(diǎn)猫胁。
具體做法如下：
1、在開始排序前跛锌，掃描對應(yīng)的存儲空間弃秆，將入度為 的頂點(diǎn)均入隊(duì)列。
2髓帽、只要隊(duì)列非空菠赚，就從隊(duì)首取出入度為 的頂點(diǎn)，將這個(gè)頂點(diǎn)輸出到結(jié)果集中郑藏，并且將這個(gè)頂點(diǎn)的所有鄰接點(diǎn)的入度減
衡查，在減
以后，發(fā)現(xiàn)這個(gè)鄰接點(diǎn)的入度為
必盖，就繼續(xù)入隊(duì)拌牲。
最后檢查結(jié)果集中的頂點(diǎn)個(gè)數(shù)是否和課程數(shù)相同即可。
Python 代碼：
class Solution(object):
# 思想：該方法的每一步總是輸出當(dāng)前無前趨（即入度為零）的頂點(diǎn)
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int 課程門數(shù)
:type prerequisites: List[List[int]] 課程與課程之間的關(guān)系
:rtype: bool
"""
# 課程的長度
clen = len(prerequisites)
if clen == 0:
# 沒有課程歌粥，當(dāng)然可以完成課程的學(xué)習(xí)
return True
# 步驟1：統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度
# 入度數(shù)組塌忽，一開始全部為 0
in_degrees = [0 for _ in range(numCourses)]
# 鄰接表
adj = [set() for _ in range(numCourses)]
# 想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 失驶，我們用一個(gè)匹配來表示他們: [0,1]
# [0,1] 表示 1 在先土居，0 在后
# 注意：鄰接表存放的是后繼 successor 結(jié)點(diǎn)的集合
for second, first in prerequisites:
in_degrees[second] += 1
adj[first].add(second)
# print("in_degrees", in_degrees)
# 首先遍歷一遍，把所有入度為 0 的結(jié)點(diǎn)加入隊(duì)列
res = []
queue = []
# 步驟2：拓?fù)渑判蜷_始之前嬉探，先把所有入度為 0 的結(jié)點(diǎn)加入到一個(gè)隊(duì)列中
for i in range(numCourses):
if in_degrees[i] == 0:
queue.append(i)
counter = 0
while queue:
top = queue.pop(0)
counter += 1
# 步驟3：把這個(gè)結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)的入度減去 1擦耀，如果發(fā)現(xiàn)入度為 0 ，就馬上添加到隊(duì)列中
for successor in adj[top]:
in_degrees[successor] -= 1
if in_degrees[successor] == 0:
queue.append(successor)
return counter == numCourses
思路2：構(gòu)建逆鄰接表甲馋，實(shí)現(xiàn)深度優(yōu)先遍歷埂奈。思路其實(shí)也很簡單，其實(shí)就是檢測這個(gè)有向圖中有沒有環(huán)定躏，只要存在環(huán)账磺，課程就不能完成。
第 1 步：構(gòu)造逆鄰接表痊远；
第 2 步：遞歸處理每一個(gè)還沒有被訪問的結(jié)點(diǎn)垮抗；核心思想是：對于一個(gè)頂點(diǎn) vertex 來說，我們先輸出了指向它的所有頂點(diǎn)碧聪，然后再輸出自己冒版，就是這么簡單。
第 3 步：如果這個(gè)頂點(diǎn)沒有被遍歷過逞姿，就遞歸遍歷它辞嗡，把所有指向它的結(jié)點(diǎn)都輸出了捆等，再輸出自己。
注意：這個(gè)深度優(yōu)先遍歷得通過逆鄰接表實(shí)現(xiàn)续室，當(dāng)訪問一個(gè)結(jié)點(diǎn)的時(shí)候栋烤，應(yīng)該遞歸訪問它的前驅(qū)結(jié)點(diǎn)，直至前驅(qū)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)為止挺狰。
Python 代碼：
# 207. 課程表
# 現(xiàn)在你總共有 n 門課需要選明郭，記為 0 到 n-1。
# 在選修某些課程之前需要一些先修課程丰泊。 例如薯定，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 瞳购，我們用一個(gè)匹配來表示他們: [0,1]
# 給定課程總量以及它們的先決條件话侄，判斷是否可能完成所有課程的學(xué)習(xí)？
class Solution(object):
# 這里使用逆鄰接表
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int 課程門數(shù)
:type prerequisites: List[List[int]] 課程與課程之間的關(guān)系
:rtype: bool
"""
# 課程的長度
clen = len(prerequisites)
if clen == 0:
# 沒有課程苛败，當(dāng)然可以完成課程的學(xué)習(xí)
return True
# 深度優(yōu)先遍歷满葛，判斷結(jié)點(diǎn)是否訪問過
# 這里要設(shè)置 3 個(gè)狀態(tài)
# 0 就對應(yīng) False ，表示結(jié)點(diǎn)沒有訪問過
# 1 就對應(yīng) True 罢屈，表示結(jié)點(diǎn)已經(jīng)訪問過嘀韧，在深度優(yōu)先遍歷結(jié)束以后才置為 1
# 2 表示當(dāng)前正在遍歷的結(jié)點(diǎn)，如果在深度優(yōu)先遍歷的過程中缠捌，
# 有遇到狀態(tài)為 2 的結(jié)點(diǎn)锄贷，就表示這個(gè)圖中存在環(huán)
visited = [0 for _ in range(numCourses)]
# 逆鄰接表，存的是每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的集合
# 想要學(xué)習(xí)課程 0 曼月，你需要先完成課程 1 谊却，我們用一個(gè)匹配來表示他們: [0,1]
# 1 在前，0 在后
inverse_adj = [set() for _ in range(numCourses)]
for second, first in prerequisites:
inverse_adj[second].add(first)
for i in range(numCourses):
# 在遍歷的過程中哑芹，如果發(fā)現(xiàn)有環(huán)炎辨，就退出
if self.__dfs(i, inverse_adj, visited):
return False
return True
def __dfs(self, vertex, inverse_adj, visited):
"""
注意：這個(gè)遞歸方法的返回值是返回是否有環(huán)
:param vertex: 結(jié)點(diǎn)的索引
:param inverse_adj: 逆鄰接表，記錄的是當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的集合
:param visited: 記錄了結(jié)點(diǎn)是否被訪問過聪姿，2 表示當(dāng)前正在 DFS 這個(gè)結(jié)點(diǎn)
:return: 是否有環(huán)
"""
# 2 表示這個(gè)結(jié)點(diǎn)正在訪問
if visited[vertex] == 2:
# 表示遇到環(huán)
return True
if visited[vertex] == 1:
return False
visited[vertex] = 2
for precursor in inverse_adj[vertex]:
# 如果有環(huán)碴萧，就返回 True 表示有環(huán)
if self.__dfs(precursor, inverse_adj, visited):
return True
# 1 表示訪問結(jié)束
# 先把 vertex 這個(gè)結(jié)點(diǎn)的所有前驅(qū)結(jié)點(diǎn)都輸出之后，再輸出自己
visited[vertex] = 1
return False
這兩種思路都可以完成 LeetCode 第 210 題末购。
LeetCode 第 210 題：課程表 II
傳送門：210. 課程表 II破喻。
現(xiàn)在你總共有 n 門課需要選，記為
0到n-1盟榴。在選修某些課程之前需要一些先修課程曹质。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 羽德，我們用一個(gè)匹配來表示他們:
[0,1]給定課程總量以及它們的先決條件几莽，返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序。
可能會有多個(gè)正確的順序玩般，你只要返回一種就可以了银觅。如果不可能完成所有課程，返回一個(gè)空數(shù)組坏为。
示例 1:
輸入: 2, [[1,0]] 輸出: [0,1] 解釋: 總共有 2 門課程。要學(xué)習(xí)課程 1镊绪，你需要先完成課程 0匀伏。因此，正確的課程順序?yàn)?[0,1] 蝴韭。示例 2:
輸入: 4, [[1,0],[2,0],[3,1],[3,2]] 輸出: [0,1,2,3] or [0,2,1,3] 解釋: 總共有 4 門課程够颠。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2榄鉴。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后履磨。 因此，一個(gè)正確的課程順序是 [0,1,2,3] 庆尘。另一個(gè)正確的排序是 [0,2,1,3] 剃诅。說明:
- 輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣驶忌。詳情請參見圖的表示法矛辕。
- 你可以假定輸入的先決條件中沒有重復(fù)的邊。
提示:
- 這個(gè)問題相當(dāng)于查找一個(gè)循環(huán)是否存在于有向圖中付魔。如果存在循環(huán)聊品，則不存在拓?fù)渑判颍虼瞬豢赡苓x取所有課程進(jìn)行學(xué)習(xí)几苍。
- 通過 DFS 進(jìn)行拓?fù)渑判?/a> - 一個(gè)關(guān)于Coursera的精彩視頻教程（21分鐘）翻屈，介紹拓?fù)渑判虻幕靖拍睢?/li>
- 拓?fù)渑判蛞部梢酝ㄟ^ BFS 完成。
思路1：拓?fù)渑判颉?/p>
Python 代碼：
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int 課程門數(shù)
:type prerequisites: List[List[int]] 課程與課程之間的關(guān)系
:rtype: bool
"""
# 課程的長度
clen = len(prerequisites)
if clen == 0:
# 沒有課程妻坝，當(dāng)然可以完成課程的學(xué)習(xí)
return [i for i in range(numCourses)]
# 入度數(shù)組伸眶，一開始全部為 0
in_degrees = [0 for _ in range(numCourses)]
# 鄰接表
adj = [set() for _ in range(numCourses)]
# 想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 惠勒，我們用一個(gè)匹配來表示他們: [0,1]
# 1 -> 0赚抡，這里要注意：不要弄反了
for second, first in prerequisites:
in_degrees[second] += 1
adj[first].add(second)
# print("in_degrees", in_degrees)
# 首先遍歷一遍，把所有入度為 0 的結(jié)點(diǎn)加入隊(duì)列
res = []
queue = []
for i in range(numCourses):
if in_degrees[i] == 0:
queue.append(i)
while queue:
top = queue.pop(0)
res.append(top)
for successor in adj[top]:
in_degrees[successor] -= 1
if in_degrees[successor] == 0:
queue.append(successor)
if len(res) != numCourses:
return []
return res
思路2：基于逆鄰接表的深度優(yōu)先遍歷纠屋。
Python 代碼：
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int 課程門數(shù)
:type prerequisites: List[List[int]] 課程與課程之間的關(guān)系
:rtype: bool
"""
# 課程的長度
clen = len(prerequisites)
if clen == 0:
# 沒有課程涂臣，當(dāng)然可以完成課程的學(xué)習(xí)
return [i for i in range(numCourses)]
# 逆鄰接表
inverse_adj = [set() for _ in range(numCourses)]
# 想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來表示他們: [0,1]
# 1 -> 0赁遗，這里要注意：不要弄反了
for second, first in prerequisites:
inverse_adj[second].add(first)
visited = [0 for _ in range(numCourses)]
# print("in_degrees", in_degrees)
# 首先遍歷一遍署辉，把所有入度為 0 的結(jié)點(diǎn)加入隊(duì)列
res = []
for i in range(numCourses):
if self.__dfs(i,inverse_adj, visited, res):
return []
return res
def __dfs(self, vertex, inverse_adj, visited, res):
"""
注意：這個(gè)遞歸方法的返回值是返回是否有環(huán)
:param vertex: 結(jié)點(diǎn)的索引
:param inverse_adj: 逆鄰接表，記錄的是當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的集合
:param visited: 記錄了結(jié)點(diǎn)是否被訪問過岩四，2 表示當(dāng)前正在 DFS 這個(gè)結(jié)點(diǎn)
:return: 是否有環(huán)
"""
# 2 表示這個(gè)結(jié)點(diǎn)正在訪問
if visited[vertex] == 2:
# DFS 的時(shí)候如果遇到一樣的結(jié)點(diǎn)哭尝，就表示圖中有環(huán)，課程任務(wù)便不能完成
return True
if visited[vertex] == 1:
return False
# 表示正在訪問這個(gè)結(jié)點(diǎn)
visited[vertex] = 2
# 遞歸訪問前驅(qū)結(jié)點(diǎn)
for precursor in inverse_adj[vertex]:
# 如果沒有環(huán)剖煌，就返回 False材鹦，
# 執(zhí)行以后，逆拓?fù)湫蛄芯痛嬖?res 中
if self.__dfs(precursor, inverse_adj, visited, res):
return True
# 能走到這里耕姊，說明所有的前驅(qū)結(jié)點(diǎn)都訪問完了桶唐，所以可以輸出了
# 并且將這個(gè)結(jié)點(diǎn)狀態(tài)置為 1
visited[vertex] = 1
# 先把 vertex 這個(gè)結(jié)點(diǎn)的所有前驅(qū)結(jié)點(diǎn)都輸出之后，再輸出自己
res.append(vertex)
# 最后不要忘記返回 False 表示無環(huán)
return False
（本節(jié)完）
二茉兰、關(guān)鍵路徑
重要的概念：（1）關(guān)鍵路徑（理解為什么是權(quán)值最大的）（2）關(guān)鍵活動(dòng)
參考資料：
1尤泽、《大話數(shù)據(jù)結(jié)構(gòu)》
2、極客時(shí)間《算法與數(shù)據(jù)結(jié)構(gòu)之美》规脸，作者：王爭
3坯约、自己以前寫的題解：
LeetCode 題解之 207. Course Schedule（拓?fù)渑判蚰０孱} 1 ）
https://blog.csdn.net/lw_power/article/details/80795288
LeetCode 題解之 210. Course Schedule II（拓?fù)渑判蚰０孱} 2 ）
https://blog.csdn.net/lw_power/article/details/80795355
4、深入理解拓?fù)渑判颍═opological sort)
http://www.reibang.com/p/3347f54a3187
拓?fù)渑判蚝?dfs
解決一個(gè)有依賴的工程是否能夠完成莫鸭。
拓?fù)渑判蚝完P(guān)鍵路徑問題闹丐。
1、AOV 網(wǎng)：與頂點(diǎn)相關(guān)黔龟。圖中不允許有回路妇智。
2、AOE 網(wǎng)：與邊相關(guān)氏身。整個(gè)任務(wù)是否能夠完成取決于最長的關(guān)鍵路徑巍棱。
使用拓?fù)渑判蚺袛?DAG 是否有回路。
LeetCode 第 207 題：課程表
參考資料：https://blog.csdn.net/ljiabin/article/details/45846837
拓?fù)渑判虻脑恚涸谝粋€(gè)有向圖中蛋欣，每次找到一個(gè)沒有前驅(qū)節(jié)點(diǎn)的結(jié)點(diǎn)（也就是入度為 0 的結(jié)點(diǎn)）航徙，然后把它指向的結(jié)點(diǎn)的邊都去掉，==重復(fù)這個(gè)過程（BFS）==陷虎，直到所有結(jié)點(diǎn)已被找到到踏，或者沒有符合條件的節(jié)點(diǎn)（如果圖中有環(huán)存在）。
回顧一下圖的三種表示方式：
1尚猿、邊表示法（即題目中表示方法）窝稿；
2、鄰接表法凿掂；
3伴榔、鄰接矩陣表示法纹蝴。
用鄰接表存儲圖比較方便尋找入度為 的節(jié)點(diǎn)。
拓?fù)渑判蛞约巴負(fù)渑判虻膫未a：
拓?fù)渑判虻膶懛ǎ?/p>
https://blog.csdn.net/qq508618087/article/details/50748965
LeetCode 第 210 題：課程表 II
要求返回一種拓?fù)渑判虻慕Y(jié)果踪少。
參考資料：http://zxi.mytechroad.com/blog/graph/leetcode-210-course-schedule-ii/
dfs 的做法：Java 的寫法以被指向的課程作為鍵塘安。
注意：下面這個(gè) dfs 的方法，有向圖的表示以先行課程作為鍵援奢。
參考資料：拓?fù)渑判颍?a target="_blank">https://mp.weixin.qq.com/s/rRIz_rsp6I9zX-EiOjCCaQ
