Go 刷 LeetCode 系列:經(jīng)典(2)拓撲排序

「選課問題」本質(zhì)上是一個top排序問題，top排序問題其實是有向圖的遍歷問題，因此可以dfs和bfs進行解。

選課問題

現(xiàn)在你總共有 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。這是不可能的。

說明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。

你可以假定輸入的先決條件中沒有重復的邊。

提示:

這個問題相當于查找一個循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓撲排序，因此不可能選取所有課程進行學習。

相關知識

通過 DFS 進行拓撲排序 - 一個關于 Coursera 的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念。

拓撲排序也可以通過 BFS 完成。

DFS解題思路：

1，將邊緣列表轉(zhuǎn)換成逆鄰接矩陣的形式，

inverse_adj[i] 的slice表示，i的所有前綴節(jié)點

2，題目可以抽象為判斷有向圖是否可以拓撲排序（是否有環(huán)）

3，循環(huán)從每一個頂點開始深度優(yōu)先遍歷

A，當前節(jié)點標記為2（正在遍歷）

B，如果該節(jié)點沒有前綴節(jié)點（入度為0，則標記為1）

C，如果該節(jié)點有前綴節(jié)點，深度優(yōu)先遍歷

D，如果該節(jié)點的所有前綴節(jié)點都標記為1，則該節(jié)點標記為1

E，如果前綴節(jié)點中有正在遍歷的節(jié)點（2），說明有環(huán)，返回。

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])    }     /* # 深度優(yōu)先遍歷，判斷結(jié)點是否訪問過        # 這里要設置 3 個狀態(tài)        # 0 就對應 False ，表示結(jié)點沒有訪問過        # 1 就對應 True ，表示結(jié)點已經(jīng)訪問過，在深度優(yōu)先遍歷結(jié)束以后才置為 1        # 2 表示當前正在遍歷的結(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: 逆鄰接表，記錄的是當前結(jié)點的前驅(qū)結(jié)點的集合        :param nodes: 記錄了結(jié)點是否被訪問過，2 表示當前正在 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<len(prerequisites);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<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]){            //將當前節(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}

推薦閱讀

• Go 刷 LeetCode 系列：經(jīng)典（1） LRU緩存機制
  

喜歡本文的朋友，歡迎關注“Go語言中文網(wǎng)”：

Go語言中文網(wǎng)啟用微信學習交流群，歡迎加微信：274768166，投稿亦歡迎