leetcode之广度优先系列算法

• leetcode之广度优先遍历系列算法
• • 1.课程表
  • • 1.1广度优先遍历

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

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