題目鏈接：210. 課程表 II
題目描述：
現(xiàn)在你總共有 numCourses 門課需要選，記為 0 到 numCourses - 1。給你一個數(shù)組 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在選修課程 ai 前 必須 先選修 bi 。
例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示：[0,1] 。
返回你為了學完所有課程所安排的學習順序?？赡軙卸鄠€正確的順序，你只要返回 任意一種 就可以了。如果不可能完成所有課程，返回 一個空數(shù)組 。
``
數(shù)據(jù)范圍：
題解：從題目描述來看，很容易就知道是拓撲排序問題了，問題在于如何存圖，如何解答，存圖方式比較多，鄰接表、鄰接矩陣，解方面：遍歷、搜索、以及隊列都能完成該題的解答，實現(xiàn)方面很多時候還是會依賴一些語言特性，比如java、c++中有隊列，可以將度為0的點放進隊列中，每次出隊一個去邊，而在golang中數(shù)據(jù)結(jié)構(gòu)支持相對匱乏，因此可以采用遍歷或者搜索方式完成。
本次采用遍歷方式，首先記錄每個節(jié)點的入度，以及邊的關系，遍歷節(jié)點，每次選出一個度為0且未被選過的節(jié)點，然后去掉與這個節(jié)點相連的邊，一共會執(zhí)行numCourses次操作，當操作完后發(fā)現(xiàn)記錄的答案中沒有numCourses個節(jié)點，那么表示不能完成拓撲排序動作。
直接遍歷：
func findOrder(numCourses int, prerequisites [][]int) []int {
edges := make([][]int, numCourses, numCourses) // 存儲邊的關系
for i := range edges {
edges[i] = make([]int, numCourses, numCourses)
}
in := make([]int, numCourses, numCourses) // 記錄入度
for i := 0; i < len(prerequisites); i++ {
a := prerequisites[i][0]
b := prerequisites[i][1]
edges[b][a] = 1 // 表示a指向b的邊
in[a]++
}
res := make([]int, 0, numCourses)
// 遍歷入度為0的點，然后去掉這些點相連的邊
for i := 0; i < numCourses; i++ { //共numCourses次操作，
k := 0 // 記錄當前尋找的入度為0的點
for j := 0; j < numCourses; j++ { // 找一個度為0且未被遍歷過的點
if in[j] == 0 {
res = append(res, j)
in[j] = -1 // 記得標記為-1，已經(jīng)找過的路徑不再往下尋找
k = j
break
}
}
for j := 0; j < numCourses; j++ {
if edges[k][j] == 1 {
edges[k][j] = -1 // 斷開這條邊
in[j]-- //j點的入度-1
}
}
}
if len(res) != numCourses {
return []int{}
}
return res
}
上述方式采用鄰接矩陣方式來存儲圖，并且通過遍歷方式來計算答案，雖然總共只操作n次，但每次都需要找尋度為0的節(jié)點，斷開與該節(jié)點相連的邊，這樣會有很多次無效的遍歷，浪費時間，因此，我們可以進行進一步的優(yōu)化。
隊列方式：
func findOrder(numCourses int, prerequisites [][]int) []int {
edges := make([][]int, numCourses, numCourses) // 存儲邊的關系
for i := range edges {
edges[i] = make([]int, numCourses, numCourses)
}
in := make([]int, numCourses, numCourses) // 記錄入度
for i := 0; i < len(prerequisites); i++ {
a := prerequisites[i][0]
b := prerequisites[i][1]
edges[b][a] = 1 // 表示a指向b的邊
in[a]++
}
queue := make([]int, 0, numCourses)
for i := 0; i < numCourses; i++ {
if in[i] == 0 {
queue = append(queue, i)
in[i] = -1
}
}
res := make([]int, 0, numCourses) // 記錄答案
// 模擬一下隊列
for len(queue) > 0 {
cur := queue[0]
res = append(res, cur)
queue = queue[1:] // 相當于除去這個元素
// 從cur這個節(jié)點開始出發(fā)，斷邊
for i := 0; i < numCourses; i++ {
if edges[cur][i] == 1 { // 如果有邊，則減少入度
in[i]--
edges[cur][i] = -1 // 斷開這條邊
// 如果沒有依賴邊了，加入隊列中
if in[i] == 0 {
queue = append(queue, i)
}
}
}
}
if len(res) != numCourses {
return []int{}
}
return res
}
當然，前面的存儲我們都采用了鄰接矩陣方式存儲，找邊的時候只能一個個遍歷去尋找，不妨換一種思路，采用鄰接表方式來存儲，優(yōu)化一下代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-706121.html
func findOrder(numCourses int, prerequisites [][]int) []int {
edges := make([][]int, numCourses) // 存儲邊的關系
fmt.Println(len(edges))
in := make([]int, numCourses, numCourses) // 記錄入度
for i := 0; i < len(prerequisites); i++ {
u := prerequisites[i][0]
v := prerequisites[i][1]
edges[v] = append(edges[v], u) // 記錄v點指向的各個節(jié)點
in[u]++
}
queue := make([]int, 0, numCourses)
for i := 0; i < numCourses; i++ {
if in[i] == 0 {
queue = append(queue, i)
}
}
res := make([]int, 0, numCourses) // 記錄答案
// 模擬一下隊列
for len(queue) > 0 {
cur := queue[0]
res = append(res, cur)
queue = queue[1:]
// 從cur這個節(jié)點開始出發(fā)，斷邊
for _, v := range edges[cur] {
in[v]--
if in[v] == 0 {
queue = append(queue, v)
}
}
}
if len(res) != numCourses {
return []int{}
}
return res
}
這樣，每個節(jié)點最多入隊一次，也只會遍歷m條邊，假設有n個節(jié)點，那么時間復雜度為O(n+m)文章來源地址http://www.zghlxwxcb.cn/news/detail-706121.html
到了這里，關于【LeetCode】210. 課程表 II——拓撲排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
