207. 课程表【拓扑排序】【BFS】

题目

题目

分析

分析1
分析2

代码

package main

const PreAllocSize = 5

// 示例：n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
// 先决条件[1, 0]，意思是必须先上课 0，才能上课 1, 0指向1
func canFinish(numCourses int, prerequisites [][]int) bool {
    // 构造有向图，key是课程号，value是依赖这门课的课程数组
    dgMap := make(map[int][]int)   // directed graph
    for k := range prerequisites {
        if dgMap[prerequisites[k][1]] == nil {
            dgMap[prerequisites[k][1]] = make([]int, 0, PreAllocSize)
        }

        dgMap[prerequisites[k][1]] = append(dgMap[prerequisites[k][1]], prerequisites[k][0])
    }

    // fmt.Printf("dgMap is %v\n", dgMap)
    // 统计入度
    inDegree := make([]int, numCourses, numCourses)  // 初始时全部为0
    for k := range dgMap {
        // k --> 指向x
        for _, v := range dgMap[k] {
            inDegree[v] ++  // 增加入度
        }
    }

    // fmt.Printf("inDegree is %v\n", inDegree)

    // 进行类似bfs操作
    bfs(dgMap, inDegree)
    // fmt.Printf("processed dgMap is %v\n", dgMap)
    // fmt.Printf("processed inDegree is %v\n", inDegree)
    // 进行完bfs后，如果还有入度不为0的，则不行
    for _, v := range inDegree {
        if v != 0 {
            return false
        }
    }

    return true
}

// 将入度为0的放入队列，进行处理
// 队列不空进行处理：
//     处理1个(出队)，则依赖这个课程的其他课程的入度会减少
//     如果依赖此课程的其他课程，有入度为0的，则入队
// 如何标记该节点已经被访问了？从dgMap中删除
func bfs(dgMap map[int][]int, inDegree []int) {
    queue := make([]int, 0, PreAllocSize)
    for k, v := range inDegree {
        if v == 0 {
            queue = append(queue, k)   // 入度为0的，入队
        }
    }

    for len(queue) > 0 {
        node := queue[0]    // 每次处理队首元素
        queue = queue[1:]   // 出队
        // fmt.Printf("Process[%v]\n", node)

        // 防止出现环
        childNodes := dgMap[node]
        if childNodes == nil {
            continue
        }
        delete(dgMap, node)  // 删除该节点，防止出现环

        // 处理node，则子child的入度都-1，看看能不能入队
        for _, child := range childNodes {
            inDegree[child] --

            if inDegree[child] == 0 {
                // fmt.Printf("入队【%v】\n", child)
                queue = append(queue, child)  // 入队
            }
        }
    }
}