溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下leetcode中拓撲排序的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
本質上是一個top排序問題，top排序問題其實是有向圖的遍歷問題，因此可以dfs和bfs進行解。
選課問題
現在你總共有 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分鐘），介紹拓撲排序的基本概念。
拓撲排序也可以通過 BFS 完成。
DFS解題思路：
1，將邊緣列表轉換成逆鄰接矩陣的形式，
inverse_adj[i] 的slice表示，i的所有前綴節點
2，題目可以抽象為判斷有向圖是否可以拓撲排序（是否有環）
3，循環從每一個頂點開始深度優先遍歷
A，當前節點標記為2（正在遍歷）
B，如果該節點沒有前綴節點（入度為0，則標記為1）
C，如果該節點有前綴節點，深度優先遍歷
D，如果該節點的所有前綴節點都標記為1，則該節點標記為1
E，如果前綴節點中有正在遍歷的節點（2），說明有環，返回。
func canFinish(numCourses int, prerequisites [][]int) bool {inverse_adj:=make([][]int,numCourses)for i:=0;i<len(prerequisites);i++{inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])}/* # 深度優先遍歷，判斷結點是否訪問過# 這里要設置 3 個狀態# 0 就對應 False ，表示結點沒有訪問過# 1 就對應 True ，表示結點已經訪問過，在深度優先遍歷結束以后才置為 1# 2 表示當前正在遍歷的結點，如果在深度優先遍歷的過程中，# 有遇到狀態為 2 的結點，就表示這個圖中存在環*/nodes:=make([]int,numCourses)for i:=0;i<numCourses;i++{//在遍歷的過程中，如果發現有環，就退出if DFS(i,inverse_adj,nodes){return false}}return true}func DFS(i int,inverse_adj [][]int,nodes []int)bool{/*注意：這個遞歸方法的返回值是返回是否有環:param i: 結點的索引:param inverse_adj: 逆鄰接表，記錄的是當前結點的前驅結點的集合:param nodes: 記錄了結點是否被訪問過，2 表示當前正在 DFS 這個結點:return: 是否有環*/if nodes[i]==2{// 2 表示這個結點正在訪問,說明有環return true}if nodes[i]==1{return false}nodes[i]=2for _,precursor:=range(inverse_adj[i]){// 如果有環，就返回 True 表示有環if DFS(precursor,inverse_adj,nodes){return true}}// # 1 表示訪問結束nodes[i] = 1return false}
BFS解題思路
解題思路：
對課程排序是，前一篇的遞進，有向圖的top排序，采用廣度優先搜索（BFS）
首先將邊緣列表轉化成逆鄰接矩陣，并記錄每個前綴課程的入度
入度為0 的課程沒有依賴，可以先上，放入隊列
一次從隊列中取節點
A. 放入返回數據
B. 將依賴此節點的所有鄰接節點的入度減一（刪除此節點后，鄰接節點的依賴減少）
C. 將修正后入度為0 的節點放入隊列
D. 循環直至隊列為空
返回數據如果長度等于課程長度，說明沒有環，否則有環
func findOrder(numCourses int, prerequisites [][]int) []int {inverse_adj:=make([][]int,numCourses)out_degree:=make([]int,numCourses) //入度for i:=0;i<len(prerequisites);i++{//將邊緣列表轉換成逆鄰接矩陣的形式out_degree[prerequisites[i][0]]++inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])}r:=BFS(inverse_adj,out_degree)if len(r)==numCourses{return r}return nil}func BFS(inverse_adj [][]int,out_degree []int)(r []int){var q queuefor i:=0;i<len(out_degree);i++{if out_degree[i]==0{//入度為0，可以作為終點q.push(i)}}for !q.empty(){top:=q.pop()r=append([]int{top},r...)for _,precursor:=range(inverse_adj[top]){//將當前節點移除，所有前驅節點的出度減1out_degree[precursor]--if out_degree[precursor]==0{q.push(precursor)}}}return r}type queue struct{data []int}func(q*queue)empty()bool{return len(q.data)==0}func(q*queue)push(i int){q.data=append(q.data,i)}func(q*queue)pop()int{r:=q.data[len(q.data)-1]q.data=q.data[:len(q.data)-1]return r}
看完了這篇文章，相信你對“leetcode中拓撲排序的示例分析”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
