210. 课程表 II【拓扑排序】【BFS】【DFS】

题目

代码BFS

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 findOrder(numCourses int, prerequisites [][]int) []int {
    // 构造有向图，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操作
    topoSort := 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 nil
        }
    }

    return topoSort
}

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

    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]    // 每次处理队首元素
        topoSort = append(topoSort, node)
        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)  // 入队
            }
        }
    }

    return topoSort
}

代码DFS

思路：
1、将入度为0的顶点m（及其关联边）从图G中取出，则剩余的G'依然是有向无环图。
2、重新考量图G'，重复1步骤，直到所有顶点均被取出。
3、对于每一个取出的顶点m，按取出的先后顺序排列，即构成了G的拓扑排序。

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

var topoSort []int

func findOrder(numCourses int, prerequisites [][]int) []int {
    // 构造有向图，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)

    // 进行类似dfs操作
    topoSort = make([]int, 0, 1000)
    dfs(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 nil
        }
    }

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

    return topoSort
}

// 将入度为0的顶点m（及其关联边）从图G中取出，则剩余的G'依然是有向无环图。
// 重新考量图G'，重复1步骤，直到所有顶点均被取出。
// 对于每一个取出的顶点m，按取出的先后顺序排列，即构成了G的拓扑排序。
func dfs(dgMap map[int][]int, inDegree []int) {
    // fmt.Printf("inDegree is %v, topoSort is %v\n", inDegree, topoSort)
    withoutZero := true                     // 没有入度为0的了

    // 步骤一：把入度为0的拿出来处理
    tmpTopoSort := make([]int, 0, 0)        // 此次处理的topo序列
    for k := range inDegree {
        if inDegree[k] == 0 {
            tmpTopoSort = append(tmpTopoSort, k)   // 放入topo序列中
            inDegree[k] --                         // -1表示已经访问过了
            withoutZero = false
        }
    }

    // 递归停止条件
    // 遍历一遍，已经没有入度为0的节点了
    if withoutZero {
        return
    }

    // 步骤二：本次处理的入度为0的子节点，从图中删除，子节点的入度减少
    // 加入大的topo序列中
    topoSort = append(topoSort, tmpTopoSort...)
    for _, node := range tmpTopoSort {   // 处理过的入度为0的节点
        if childs, ok := dgMap[node]; ok {
            for _, child := range childs {
                inDegree[child] --       // 子节点入度减少
            }
        }
    }

    // 步骤三：重复步骤一、二
    dfs(dgMap, inDegree)           // 新的图，差异体现在inDegree
}