golang刷leetcode 经典（2）拓扑排序

func canFinish(numCourses int, prerequisites [][]int) bool {
    inverse_adj:=make([][]int,numCourses)
    for i:=0;i<len(prerequisites);i++{
        inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])
    }
     /* # 深度优先遍历，判断结点是否访问过
        # 这里要设置 3 个状态
        # 0 就对应 False ，表示结点没有访问过
        # 1 就对应 True ，表示结点已经访问过，在深度优先遍历结束以后才置为 1
        # 2 表示当前正在遍历的结点，如果在深度优先遍历的过程中，
        # 有遇到状态为 2 的结点，就表示这个图中存在环
        */
    nodes:=make([]int,numCourses)
    for i:=0;i<numCourses;i++{
        //在遍历的过程中，如果发现有环，就退出
        if DFS(i,inverse_adj,nodes){
            return false
        }
    }
    return true
}


func DFS(i int,inverse_adj [][]int,nodes []int)bool{
    /*
     注意：这个递归方法的返回值是返回是否有环
        :param i: 结点的索引
        :param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合
        :param nodes: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点
        :return: 是否有环
        */
    if nodes[i]==2{
      // 2 表示这个结点正在访问,说明有环
        return true
    }
    if nodes[i]==1{
        return false
    }
    nodes[i]=2
    for _,precursor:=range(inverse_adj[i]){
        // 如果有环，就返回 True 表示有环
        if DFS(precursor,inverse_adj,nodes){
            return true
        }
    }
    // # 1 表示访问结束
        nodes[i] = 1
    return false
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    inverse_adj:=make([][]int,numCourses)
    out_degree:=make([]int,numCourses) //入度
    for i:=0;i<len(prerequisites);i++{
        //将边缘列表转换成逆邻接矩阵的形式
        out_degree[prerequisites[i][0]]++
        inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])   
    }
    r:=BFS(inverse_adj,out_degree)
    if len(r)==numCourses{
        return r
    }
    return nil
}


func BFS(inverse_adj [][]int,out_degree []int)(r []int){
    var q queue
    for i:=0;i<len(out_degree);i++{
        if out_degree[i]==0{
            //入度为0，可以作为终点
            q.push(i)
        }
    }
    
    for !q.empty(){
        top:=q.pop()
        r=append([]int{top},r...)
        for _,precursor:=range(inverse_adj[top]){
            //将当前节点移除，所有前驱节点的出度减1
            out_degree[precursor]--
            if out_degree[precursor]==0{
                q.push(precursor)
            }
        }
    }
    return r
}


type queue struct{
    data []int
}


func(q*queue)empty()bool{
    return len(q.data)==0
}


func(q*queue)push(i int){
    q.data=append(q.data,i)
}


func(q*queue)pop()int{
    r:=q.data[len(q.data)-1]
    q.data=q.data[:len(q.data)-1]
    return r
}