课程表 循环依赖 拓扑排序 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
}```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53