Function canFinishBFS

course_schedule_207/solution.go:8–33

Note: study again. BFS cycle detection based on topological sorting (Kahn’s algorithm). If we don't visit every vertex in the topological sort, then we've ran into a cycle.

(numCourses int, prerequisites [][]int)

// If we don't visit every vertex in the topological sort, then we've
// ran into a cycle.
func canFinishBFS(numCourses int, prerequisites [][]int) bool {
	if len(prerequisites) == 0 {
		return true
	}

	adjList := make(map[int][]int)
	for _, pre := range prerequisites {
		adjList[pre[0]] = append(adjList[pre[0]], pre[1])
	}

	// calculate the in-degree for each vertex
	inDegrees := make([]int, numCourses)
	for _, prereq := range prerequisites {
		inDegrees[prereq[1]]++
	}

	// enqueue all verticies with in-degree of 0
	zeroInQueue := make([]int, 0)
	for course, inDegree := range inDegrees {
		if inDegree == 0 {
			zeroInQueue = append(zeroInQueue, course)
		}
	}

	return !hasCycleBFS(adjList, zeroInQueue, inDegrees, numCourses)
}

func hasCycleBFS(adjList map[int][]int, zeroInQueue []int,
	inDegrees []int, numVerticies int) bool {