| 33 | } |
| 34 | |
| 35 | func hasCycleBFS(adjList map[int][]int, zeroInQueue []int, |
| 36 | inDegrees []int, numVerticies int) bool { |
| 37 | |
| 38 | seen := 0 |
| 39 | for len(zeroInQueue) != 0 { |
| 40 | // dequeue a zero in-degree vertex |
| 41 | v := zeroInQueue[0] |
| 42 | zeroInQueue = zeroInQueue[1:] |
| 43 | seen++ |
| 44 | |
| 45 | // for each prereq adjacent to v, decrement it's in-degree |
| 46 | // and enqueue it if it's in-degree became 0. |
| 47 | for _, prereq := range adjList[v] { |
| 48 | inDegrees[prereq]-- |
| 49 | if inDegrees[prereq] == 0 { |
| 50 | zeroInQueue = append(zeroInQueue, prereq) |
| 51 | } |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | // if we did not see each vertex along the topological sort |
| 56 | if seen != numVerticies { |
| 57 | return true |
| 58 | } |
| 59 | |
| 60 | return false |
| 61 | } |
| 62 | |
| 63 | // DFS cycle detection based on coloring the recursive path as "in progress" |
| 64 | // or not. If we get back to an "in progress" vertex, it's a part of a cycle. |