leetcode之广度优先遍历系列算法

1.课程表

1.1广度优先遍历

func canFinish(numCourses int, prerequisites [][]int) bool {
          
   
    var (
        edges = make([][]int, numCourses)  //邻接表
        indeg = make([]int, numCourses)  //入度数组
    )

    for i :=0;i<len(prerequisites);i++ {
          
   
        edges[prerequisites[i][1]] = append(edges[prerequisites[i][1]], prerequisites[i][0])
        indeg[prerequisites[i][0]]++  //求课的初始入度值
    }

    q := []int{
          
   }
    for i := 0; i < numCourses; i++ {
          
   
        if indeg[i] == 0 {
          
   
            q = append(q, i)  //所有入度为0的课入列
        }
    }
    
    count :=0
    for len(q) > 0 {
          
   
        u := q[0]
        q = q[1:]
        count++  //选课数+1
       for i :=0;i<len(edges[u]);i++{
          
   
           indeg[edges[u][i]]-- // 依赖它的后续课的入度-1
           if  indeg[edges[u][i]]==0{
          
    // 如果因此减为0，入列
              q=append(q, edges[u][i])
           }
       }  
    }
    return count == numCourses// 选了的课等于总课数，true，否则false
}