课程表 循环依赖 拓扑排序 go语言

学会拓扑排序题目的基本解法

• res数组 记录上课顺序
• g 记录学了课程i 能解锁的课程j
• indeg 记录每个课程的入度
• q 记录入度为0的课程 for循环q去解放其他课程

本题来自力扣课程表

func findOrder(numCourses int, prerequisites [][]int) []int {res := []int{}//建一个二维数组记录每个课程的依赖关系g := make([][]int,numCourses)//记录每个结点入度的数组indeg := make([]int,numCourses)//处理关系 //记录入度 //记录某个课程学了之后能减少哪个课程的入度for _,v := range prerequisites {in := v[1]out := v[0]g[in] = append(g[in],out)indeg[out]++}//入度为0的结点进入队列q := []int{}for i := range indeg {if indeg[i] == 0 {q = append(q,i)}}//遍历入度为0的结点 解放入度不为0的结点for len(q) > 0 {node := q[0]q = q[1:]res = append(res,node)for _,v := range g[node] {indeg[v]--if indeg[v] == 0 {q = append(q,v)}}}//结果数组和课程数量不同if len(res) != numCourses {return []int{}}return res
}```