leetcode階段總結——拓撲排序
?

leetcode中經常出現的題型之一。其中，拓撲排序的概念可以參考這里，這里主要總結一下前300題中出現的幾個關于拓撲排序的題，以待之后復習的時候查找。

leetcode207 課程表

??? 現在你總共有 n 門課需要選，記為 0 到 n-1。
??? 在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]
??? 給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學習？

??? 示例 1:

??????? 輸入: 2, [[1,0]]
??????? 輸出: true
??????? 解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。

??? 示例 2:

??????? 輸入: 2, [[1,0],[0,1]]
??????? 輸出: false
??????? 解釋: 總共有 2 門課程。學習課程 1 之前，你需要先完成?課程 0；并且學習課程 0 之前，你還應先完成課程 1。這是不可能的。

??? 說明:

??????? 輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。
??????? 你可以假定輸入的先決條件中沒有重復的邊。

??? 提示:

??????? 這個問題相當于查找一個循環是否存在于有向圖中。如果存在循環，則不存在拓撲排序，因此不可能選取所有課程進行學習。
??????? 通過 DFS 進行拓撲排序 - 一個關于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。
??????? ?
??????

本題是一道經典的「拓撲排序」問題。

給定一個包含 nnn 個節點的有向圖 GGG，我們給出它的節點編號的一種排列，如果滿足：

??? 對于圖 GGG 中的任意一條有向邊 (u,v)(u, v)(u,v)，uuu 在排列中都出現在 vvv 的前面。

那么稱該排列是圖 GGG 的「拓撲排序」。根據上述的定義，我們可以得出兩個結論：

??? 如果圖 GGG 中存在環（即圖 GGG 不是「有向無環圖」），那么圖 GGG 不存在拓撲排序。這是因為假設圖中存在環 x1,x2,? ,xn,x1x_1, x_2, \cdots, x_n, x_1x1?,x2?,?,xn?,x1?，那么 x1x_1x1? 在排列中必須出現在 xnx_nxn? 的前面，但 xnx_nxn? 同時也必須出現在 x1x_1x1? 的前面，因此不存在一個滿足要求的排列，也就不存在拓撲排序；

??? 如果圖 GGG 是有向無環圖，那么它的拓撲排序可能不止一種。舉一個最極端的例子，如果圖 GGG 值包含 nnn 個節點卻沒有任何邊，那么任意一種編號的排列都可以作為拓撲排序。

有了上述的簡單分析，我們就可以將本題建模成一個求拓撲排序的問題了：

??? 我們將每一門課看成一個節點；

??? 如果想要學習課程 AAA 之前必須完成課程 BBB，那么我們從 BBB 到 AAA 連接一條有向邊。這樣以來，在拓撲排序中，BBB 一定出現在 AAA 的前面。

求出該圖是否存在拓撲排序，就可以判斷是否有一種符合要求的課程學習順序。事實上，由于求出一種拓撲排序方法的最優時間復雜度為 O(n+m)O(n+m)O(n+m)，其中 nnn 和 mmm 分別是有向圖 GGG 的節點數和邊數，方法見 210. 課程表 II 的官方題解。而判斷圖 GGG 是否存在拓撲排序，至少也要對其進行一次完整的遍歷，時間復雜度也為 O(n+m)O(n+m)O(n+m)。因此不可能存在一種僅判斷圖是否存在拓撲排序的方法，它的時間復雜度在漸進意義上嚴格優于 O(n+m)O(n+m)O(n+m)。這樣一來，我們使用和 210. 課程表 II 完全相同的方法，但無需使用數據結構記錄實際的拓撲排序。為了敘述的完整性，下面的兩種方法與 210. 課程表 II 的官方題解 完全相同，但在「算法」部分后的「優化」部分說明了如何省去對應的數據結構。
方法一：深度優先搜索

思路

我們可以將深度優先搜索的流程與拓撲排序的求解聯系起來，用一個棧來存儲所有已經搜索完成的節點。

??? 對于一個節點 uuu，如果它的所有相鄰節點都已經搜索完成，那么在搜索回溯到 uuu 的時候，uuu 本身也會變成一個已經搜索完成的節點。這里的「相鄰節點」指的是從 uuu 出發通過一條有向邊可以到達的所有節點。

假設我們當前搜索到了節點 uuu，如果它的所有相鄰節點都已經搜索完成，那么這些節點都已經在棧中了，此時我們就可以把 uuu 入棧。可以發現，如果我們從棧頂往棧底的順序看，由于 uuu 處于棧頂的位置，那么 uuu 出現在所有 uuu 的相鄰節點的前面。因此對于 uuu 這個節點而言，它是滿足拓撲排序的要求的。

這樣以來，我們對圖進行一遍深度優先搜索。當每個節點進行回溯的時候，我們把該節點放入棧中。最終從棧頂到棧底的序列就是一種拓撲排序。

算法

對于圖中的任意一個節點，它在搜索的過程中有三種狀態，即：

??? 「未搜索」：我們還沒有搜索到這個節點；

??? 「搜索中」：我們搜索過這個節點，但還沒有回溯到該節點，即該節點還沒有入棧，還有相鄰的節點沒有搜索完成）；

??? 「已完成」：我們搜索過并且回溯過這個節點，即該節點已經入棧，并且所有該節點的相鄰節點都出現在棧的更底部的位置，滿足拓撲排序的要求。

通過上述的三種狀態，我們就可以給出使用深度優先搜索得到拓撲排序的算法流程，在每一輪的搜索搜索開始時，我們任取一個「未搜索」的節點開始進行深度優先搜索。

??? 我們將當前搜索的節點 uuu 標記為「搜索中」，遍歷該節點的每一個相鄰節點 vvv：

??????? 如果 vvv 為「未搜索」，那么我們開始搜索 vvv，待搜索完成回溯到 uuu；

??????? 如果 vvv 為「搜索中」，那么我們就找到了圖中的一個環，因此是不存在拓撲排序的；

??????? 如果 vvv 為「已完成」，那么說明 vvv 已經在棧中了，而 uuu 還不在棧中，因此 uuu 無論何時入棧都不會影響到 (u,v)(u, v)(u,v) 之前的拓撲關系，以及不用進行任何操作。

??? 當 uuu 的所有相鄰節點都為「已完成」時，我們將 uuu 放入棧中，并將其標記為「已完成」。

在整個深度優先搜索的過程結束后，如果我們沒有找到圖中的環，那么棧中存儲這所有的 nnn 個節點，從棧頂到棧底的順序即為一種拓撲排序。

class Solution {static Map<Integer,List<Integer>> map;static int [] state;public boolean canFinish(int numCourses, int[][] p) {if(p==null){return true;}map=new HashMap<Integer,List<Integer>>();state=new int[numCourses];for(int i=0;i<p.length;i++){if(map.containsKey(p[i][0])){map.get(p[i][0]).add(p[i][1]);}else{List<Integer> list=new ArrayList<Integer>();list.add(p[i][1]);map.put(p[i][0], list);}}for(int i=0;i<p.length;i++){if(state[p[i][0]]==2){continue;}if(!dfs(p[i][0])){return false;}}return true;} public static boolean dfs(Integer i){if(state[i]==2) return true;if(state[i]==1) return false;state[i]=1;if(map.containsKey(i)){List<Integer> list=map.get(i);for(int j:list){if(!dfs(j)){return false;}}}state[i]=2;return true;} }

?

方法二入度表法：

???????

題意解釋

??? 一共有 n 門課要上，編號為 0 ~ n-1。
??? 先決條件[1, 0]，意思是必須先上課 0，才能上課 1。
??? 給你 n 、和一個先決條件表，請你判斷能否完成所有課程。

再舉個生活的例子

??? 先穿內褲再穿褲子，先穿打底再穿外套，先穿衣服再戴帽子，是約定俗成的。
??? 內褲外穿、光著身子戴帽子等，都會有點奇怪。
??? 我們遵循穿衣的一條條先后規則，用一串順序行為，把衣服一件件穿上。
??? 我們遵循課程之間的先后規則，找到一種上課順序，把所有課一節節上完。

??? 示例：n = 6，先決條件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
??? 課 0, 1, 2 沒有先修課，可以直接選。其余的課，都有兩門先修課。
??? 我們用有向圖來展現這種依賴關系（做事情的先后關系）：
???
??? 這種叫 有向無環圖，把一個 有向無環圖 轉成 線性的排序 就叫 拓撲排序。
??? 有向圖有 入度 和 出度 的概念：
??????? 如果存在一條有向邊 A --> B，則這條邊給 A 增加了 1 個出度，給 B 增加了 1 個入度。
??? 所以，頂點 0、1、2 的入度為 0。頂點 3、4、5 的入度為 2。

每次只能選你能上的課

??? 每次只能選入度為 0 的課，因為它不依賴別的課，是當下你能上的課。
??? 假設選了 0，課 3 的先修課少了一門，入度由 2 變 1。
??? 接著選 1，導致課 3 的入度變 0，課 4 的入度由 2 變 1。
??? 接著選 2，導致課 4 的入度變 0。
??? 現在，課 3 和課 4 的入度為 0。繼續選入度為 0 的課……直到選不到入度為 0 的課。

這很像 BFS

??? 讓入度為 0 的課入列，它們是能直接選的課。
??? 然后逐個出列，出列代表著課被選，需要減小相關課的入度。
??? 如果相關課的入度新變為 0，安排它入列、再出列……直到沒有入度為 0 的課可入列。

BFS 前的準備工作

??? 每門課的入度需要被記錄，我們關心入度值的變化。
??? 課程之間的依賴關系也要被記錄，我們關心選當前課會減小哪些課的入度。
??? 因此我們需要選擇合適的數據結構，去存這些數據：
??? 入度數組：課號 0 到 n - 1 作為索引，通過遍歷先決條件表求出對應的初始入度。
??? 鄰接表：用哈希表記錄依賴關系（也可以用二維矩陣，但有點大）
??????? key：課號
??????? value：依賴這門課的后續課（數組）

怎么判斷能否修完所有課？

??? BFS 結束時，如果仍有課的入度不為 0，無法被選，完成不了所有課。否則，能找到一種順序把所有課上完。
??? 或者：用一個變量 count 記錄入列的頂點個數，最后判斷 count 是否等于總課程數。

代碼

public boolean canFinish(int numCourses, int[][]p ){if(p==null){return true;}int result=0; //記錄節點被哪些節點所依賴Map<Integer,List<Integer>> map=new HashMap<Integer,List<Integer>>();int [] indegree=new int[numCourses];for(int i=0;i<p.length;i++){if(map.containsKey(p[i][1])){map.get(p[i][1]).add(p[i][0]);}else{List<Integer> list=new ArrayList<Integer>();list.add(p[i][0]);map.put(p[i][1], list);}indegree[p[i][0]]++;}Queue<Integer> stack=new LinkedList<Integer>();for(int i=0;i<numCourses;i++){if(indegree[i]==0){stack.offer(i);}}while(!stack.isEmpty()){int numZero=stack.poll();result++;if(map.containsKey(numZero)){List<Integer> list=map.get(numZero);for(int num:list){indegree[num]--;if(indegree[num]==0){stack.offer(num);}}}}return result==numCourses;}

?

leetcode210 課程表2

??? 現在你總共有 n 門課需要選，記為 0 到 n-1。
??? 在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]
??? 給定課程總量以及它們的先決條件，返回你為了學完所有課程所安排的學習順序。
??? 可能會有多個正確的順序，你只要返回一種就可以了。如果不可能完成所有課程，返回一個空數組。

??? 示例 1:

??????? 輸入: 2, [[1,0]]
??????? 輸出: [0,1]
??????? 解釋: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0。因此，正確的課程順序為 [0,1] 。

??? 示例 2:

??????? 輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
??????? 輸出: [0,1,2,3] or [0,2,1,3]
??????? 解釋: 總共有 4 門課程。要學習課程 3，你應該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應該排在課程 0 之后。
???????????? 因此，一個正確的課程順序是 [0,1,2,3] 。另一個正確的排序是 [0,2,1,3] 。

??? 說明:

??????? 輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。
??????? 你可以假定輸入的先決條件中沒有重復的邊。

??? 提示:

??????? 這個問題相當于查找一個循環是否存在于有向圖中。如果存在循環，則不存在拓撲排序，因此不可能選取所有課程進行學習。
??????? 通過 DFS 進行拓撲排序 - 一個關于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。
??????? ?
??????? 拓撲排序也可以通過 BFS 完成。

如果我們要返回的不僅僅是排序的可能性，而是排序結果，應該怎么辦？其實很容易想通，在入度表元素變為零/某個元素的記憶化遞歸完成的時候，就說明這個元素已經“無牽無掛”，沒有前向節點或前向節點已經加入排序列表中，可以將這個元素加入列表中了。如果忘記了思路或是看不懂了，更詳細的解析也可以看這里，寫的非常清楚。

代碼和之前的基本相同。

入度表法

??? class Solution:
??????? def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
??????????? ##迭代方法
??????????? adjacent = [[] for i in range(numCourses)]
??????????? indegree = [0] * numCourses
??????????? result = []
??????????? for cur,pre in prerequisites:
??????????????? indegree[cur] += 1
??????????????? adjacent[pre].append(cur)
??????????? from collections import deque
??????????? queue = deque()
??????????? for i in range(numCourses):
??????????????? if not indegree[i]:
??????????????????? queue.append(i)
??????????????????? result.append(i)
??????????? while queue:
??????????????? #element = queue.popleft()
??????????????? element = queue.pop()
??????????????? numCourses -= 1
??????????????? for neighbor in adjacent[element]:
??????????????????? indegree[neighbor] -= 1
??????????????????? if not indegree[neighbor]:
??????????????????????? queue.append(neighbor)
??????????????????????? result.append(neighbor)
??????????? #print(result)
??????????? return result if numCourses == 0 else []

遞歸法

??? class Solution:
??????? def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
??????????? def dfs(i):
??????????????? if flag[i] == -1:
??????????????????? return True
??????????????? if flag[i] == 1:
??????????????????? return False
??????????????? flag[i] = 1
??????????????? for neighbor in adjacent[i]:
??????????????????? if not dfs(neighbor):
??????????????????????? return False
??????????????? flag[i] = -1
??????????????? result.append(i)
??????????????? return True
??? ?
??????????? adjacent = [[] for _ in range(numCourses)]
??????????? flag = [0] * numCourses
??????????? result = []
??????????? for cur,pre in prerequisites:
??????????????? adjacent[pre].append(cur)
??????????? for j in range(numCourses):
??????????????? if not dfs(j):
??????????????????? return []
??????????? return result[::-1]

leetcode269 火星詞典

??? 現有一種使用字母的全新語言，這門語言的字母順序與英語順序不同。
??? 假設，您并不知道其中字母之間的先后順序。但是，會收到詞典中獲得一個 不為空的 單詞列表。因為是從詞典中獲得的，所以該單詞列表內的單詞已經 按這門新語言的字母順序進行了排序。
??? 您需要根據這個輸入的列表，還原出此語言中已知的字母順序。

??? 示例 1：

??????? 輸入:
??????? [
????????? "wrt",
????????? "wrf",
????????? "er",
????????? "ett",
????????? "rftt"
??????? ]
??????? ?
??????? 輸出: "wertf"

??? 示例 2：

??????? 輸入:
??????? [
????????? "z",
????????? "x"
??????? ]
??????? ?
??????? 輸出: "zx"
??????? ?
??????? 示例 3：

??? 輸入: [ "z", "x", "z" ]

??????? 輸出: ""
??????? ?
??????? 解釋: 此順序是非法的，因此返回 ""。

??? 注意：

??????? 你可以默認輸入的全部都是小寫字母
??????? 假如，a 的字母排列順序優先于 b，那么在給定的詞典當中 a 定先出現在 b 前面
??????? 若給定的順序是不合法的，則返回空字符串即可
??????? 若存在多種可能的合法字母順序，請返回其中任意一種順序即可

從拓撲排序的角度來說，這個題其實不難，難點在于如何將詞典這一問題抽象成拓撲排序。實際上，輸入所反映的字母的先后順序，也就是計算圖中節點的指向順序。

??? from collections import defaultdict, deque
??? class Solution:
??????? def alienOrder(self, words: List[str]) -> str:
??????????? ## 統計節點個數
??????????? nodes = set("".join(words))
??????????? ## 建立計算圖
??????????? adjacent = defaultdict(list)
??????????? indegree = dict(zip(list(nodes),[0] * len(nodes)))
??????????? for i in range(len(words) - 1):
??????????????? word1,word2 = words[i],words[i + 1]
??????????????? lenWord = min(len(word1),len(word2))
??????????????? for j in range(lenWord):
??????????????????? if word1[j] != word2[j]:
??????????????????????? adjacent[word1[j]].append(word2[j])
??????????????????????? indegree[word2[j]] += 1
??????????????????????? break
??????????? ## 拓撲排序
??????????? result = []
??????????? queue = [i for i in indegree if indegree[i] == 0]
??????????? while queue:
??????????????? element = queue.pop()
??????????????? result.append(element)
??????????????? for neighbor in adjacent[element]:
??????????????????? indegree[neighbor] -= 1
??????????????????? if indegree[neighbor] == 0: queue.append(neighbor)
??? ?
??????????? return "".join(result) if len(result) == len(nodes) else ""

在結果是否有效的判定中，之前的判定條件是numCourses == 0，這里的判斷條件是len(result) == len(nodes)，其實是一樣的，本質都是判斷是否所有節點都被遍歷到。

leetcode261 以圖判樹

??? 給定從 0 到 n-1 標號的 n 個結點，和一個無向邊列表（每條邊以結點對來表示），請編寫一個函數用來判斷這些邊是否能夠形成一個合法有效的樹結構。

??? 示例 1：

??????? 輸入: n = 5, 邊列表 edges = [[0,1], [0,2], [0,3], [1,4]]
??????? 輸出: true

??? 示例 2:

??????? 輸入: n = 5, 邊列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
??????? 輸出: false

??? 注意： 你可以假定邊列表 edges 中不會出現重復的邊。由于所有的邊是無向邊，邊 [0,1] 和邊 [1,0] 是相同的，因此不會同時出現在邊列表 edges 中。

這個題和前面的問題有一個不同之處，就是前面的問題中，我們只需要考慮圖是否成環的問題，所有的點都必然是連通的。而這個問題中，我們還要考慮是否有不被其他點連通的點存在。

其他的思路幾乎相同，需要注意的就是判斷條件有兩個：1.所有的點都聯通，這由所有的點都被遍歷過來判斷；2.沒有環，這由邊的計數來判斷，和之前的numCourse對應。

??? class Solution:
??????? def validTree(self, n: int, edges: List[List[int]]) -> bool:
??????????? adjacent = [[] for _ in range(n)]
??????????? for x,y in edges:
??????????????? adjacent[x].append(y)
??????????????? adjacent[y].append(x)
??????????? visited = set()
??? ?
??????????? def helper(prev,node):
??????????????? if node in visited: return False
??????????????? visited.add(node)
??????????????? for neighbor in adjacent[node]:
??????????????????? if neighbor == prev: continue
??????????????????? if not helper(node,neighbor): return False
??????????????? return True
??? ?
??????????? return helper(None,0) and len(visited) == n

另一種方法

??? class Solution:
??????? def validTree(self, n: int, edges: List[List[int]]) -> bool:
??????????? ##從一個點出發，能遍歷所有的點，保證的是連通性
??????????? ##無環性是這樣保證的：從一個點出發，應該只能到達另一個點一次
??????????? ##如果不重復路徑可以到達兩次，那就是有環
??????????? ##我們記錄下已經遍歷過的點，如果有環，那么就會有已經遍歷過的點再次出現，也就是有一條邊沒有被從總數中減掉
??????????? ##那么就有lenEdges != 0
??????????? ##這一套也可以改成遞歸，省個棧，改起來很容易
??????????? ##最后就是注意集合比列表快得多，如果不要求順序，還是優先用這個
??????????? adjacent = [[] for _ in range(n)]
??????????? for x,y in edges:
??????????????? adjacent[x].append(y)
??????????????? adjacent[y].append(x)
??????????? visited = {0}
??????????? stack = [0]
??????????? lenEdges = len(edges)
??????????? while stack:
??????????????? element = stack.pop()
??????????????? for neighbor in adjacent[element]:
??????????????????? if not neighbor in visited:
??????????????????????? lenEdges -= 1
??????????????????????? visited.add(neighbor)
??????????????????????? stack.append(neighbor)
??????????? return len(visited) == n and lenEdges == 0?? ?
————————————————
版權聲明：本文為CSDN博主「菲菲小姐」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_39655021/article/details/103752005

總結

以上是生活随笔為你收集整理的leetcode阶段总结——拓扑排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。