小編給大家分享一下leetcode中拓撲排序的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
創(chuàng)新互聯(lián)公司IDC提供業(yè)務(wù):成都移動機房托管,成都服務(wù)器租用,成都移動機房托管,重慶服務(wù)器租用等四川省內(nèi)主機托管與主機租用業(yè)務(wù);數(shù)據(jù)中心含:雙線機房,BGP機房,電信機房,移動機房,聯(lián)通機房。
本質(zhì)上是一個top排序問題，top排序問題其實是有向圖的遍歷問題，因此可以dfs和bfs進行解。
選課問題
現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1。
在選修某些課程之前需要一些先修課程。例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [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ù)的邊。
提示:
這個問題相當(dāng)于查找一個循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓撲排序，因此不可能選取所有課程進行學(xué)習(xí)。
相關(guān)知識
通過 DFS 進行拓撲排序 - 一個關(guān)于 Coursera 的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。
拓撲排序也可以通過 BFS 完成。
DFS解題思路：
1，將邊緣列表轉(zhuǎn)換成逆鄰接矩陣的形式，
inverse_adj[i] 的slice表示，i的所有前綴節(jié)點
2，題目可以抽象為判斷有向圖是否可以拓撲排序（是否有環(huán)）
3，循環(huán)從每一個頂點開始深度優(yōu)先遍歷
A，當(dāng)前節(jié)點標(biāo)記為2（正在遍歷）
B，如果該節(jié)點沒有前綴節(jié)點（入度為0，則標(biāo)記為1）
C，如果該節(jié)點有前綴節(jié)點，深度優(yōu)先遍歷
D，如果該節(jié)點的所有前綴節(jié)點都標(biāo)記為1，則該節(jié)點標(biāo)記為1
E，如果前綴節(jié)點中有正在遍歷的節(jié)點（2），說明有環(huán)，返回。
func canFinish(numCourses int, prerequisites [][]int) bool { inverse_adj:=make([][]int,numCourses) for i:=0;i inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0]) } /* # 深度優(yōu)先遍歷，判斷結(jié)點是否訪問過 # 這里要設(shè)置 3 個狀態(tài) # 0 就對應(yīng) False ，表示結(jié)點沒有訪問過 # 1 就對應(yīng) True ，表示結(jié)點已經(jīng)訪問過，在深度優(yōu)先遍歷結(jié)束以后才置為 1 # 2 表示當(dāng)前正在遍歷的結(jié)點，如果在深度優(yōu)先遍歷的過程中， # 有遇到狀態(tài)為 2 的結(jié)點，就表示這個圖中存在環(huán) */ nodes:=make([]int,numCourses) for i:=0;i //在遍歷的過程中，如果發(fā)現(xiàn)有環(huán)，就退出 if DFS(i,inverse_adj,nodes){ return false } } return true}
func DFS(i int,inverse_adj [][]int,nodes []int)bool{ /* 注意：這個遞歸方法的返回值是返回是否有環(huán) :param i: 結(jié)點的索引 :param inverse_adj: 逆鄰接表，記錄的是當(dāng)前結(jié)點的前驅(qū)結(jié)點的集合 :param nodes: 記錄了結(jié)點是否被訪問過，2 表示當(dāng)前正在 DFS 這個結(jié)點 :return: 是否有環(huán) */ if nodes[i]==2{ // 2 表示這個結(jié)點正在訪問,說明有環(huán) return true } if nodes[i]==1{ return false } nodes[i]=2 for _,precursor:=range(inverse_adj[i]){ // 如果有環(huán)，就返回 True 表示有環(huán) if DFS(precursor,inverse_adj,nodes){ return true } } // # 1 表示訪問結(jié)束 nodes[i] = 1 return false}
BFS解題思路
解題思路：
對課程排序是，前一篇的遞進，有向圖的top排序，采用廣度優(yōu)先搜索（BFS）
首先將邊緣列表轉(zhuǎn)化成逆鄰接矩陣，并記錄每個前綴課程的入度
入度為0 的課程沒有依賴，可以先上，放入隊列
一次從隊列中取節(jié)點
A. 放入返回數(shù)據(jù)
B. 將依賴此節(jié)點的所有鄰接節(jié)點的入度減一（刪除此節(jié)點后，鄰接節(jié)點的依賴減少）
C. 將修正后入度為0 的節(jié)點放入隊列
D. 循環(huán)直至隊列為空
返回數(shù)據(jù)如果長度等于課程長度，說明沒有環(huán)，否則有環(huán)
func findOrder(numCourses int, prerequisites [][]int) []int { inverse_adj:=make([][]int,numCourses) out_degree:=make([]int,numCourses) //入度 for i:=0;i //將邊緣列表轉(zhuǎn)換成逆鄰接矩陣的形式 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 queue for i:=0;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]){ //將當(dāng)前節(jié)點移除，所有前驅(qū)節(jié)點的出度減1 out_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}
看完了這篇文章，相信你對“l(fā)eetcode中拓撲排序的示例分析”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
本文標(biāo)題：leetcode中拓撲排序的示例分析
URL標(biāo)題：
http://weahome.cn/article/jhejgj.html
重慶分公司
重慶分公司
