Kahn's Algorithm

1. 1.Course Schedule
   Kahn's Algorithm: return processedCount == n (check for dependency deadlock cycle)medium
2. 2.Course Schedule II
   Return valid topological ordering array built from Kahn's Indegree 0 Queuemedium
3. 3.Topological Sort
   Standard Kahn's BFS topological sort templatemedium
4. 4.Alien Dictionary
   Build character dependency graph + Kahn's indegree queue (check prefix rule & cycle deadlock)hard
5. 5.Parallel Courses
   Kahn's BFS level-by-level queue size loop counting minimum semesters requiredmedium
6. 6.Parallel Courses III
   Kahn + DP on DAG: start[v] = max(start[v], finish[u]) for task completion timeshard
7. 7.Find All Possible Recipes From Given Supplies
   Recipe ingredient dependency graph initialized with supplies having indegree 0medium
8. 8.Sequence Reconstruction
   Verify unique topological ordering (Kahn's queue must never contain >1 node at any step)medium
9. 9.Minimum Semesters to Finish Courses
   Kahn's level-order queue size loop for semester wave countingmedium
10. 10.Build Order
    Package dependency DAG ordering using Kahn's Algorithmmedium
11. 11.Task Scheduling with Dependencies
    Parallel task queue execution where indegree 0 represents ready tasksmedium
12. 12.Largest Color Value in a Directed Graph
    Kahn Topo Sort + DP state dp[u][color] tracking max color frequencies along pathshard
13. 13.Sort Items by Groups Respecting Dependencies
    Dual Kahn's Topo Sort on group DAG & item DAGhard
14. 14.Find Eventual Safe States
    Reverse graph edges + Kahn's BFS starting from 0 out-degree terminal nodesmedium
15. 15.Detect Cycle in Directed Graph Using Kahn
    Cycle detected if len(order) < n when queue emptiesmedium

1. 16.Minimum Time to Complete All Tasks
   Task duration optimization + Kahn's Topo ordermedium
2. 17.Critical Path in DAG
   Kahn's Algorithm + DP finding longest duration path in project networkshard
3. 18.DAG Layer Processing
   Grouping nodes into parallel dependency waves using level-order Kahnmedium
4. 19.Package Installation Order
   Package manager dependency resolutionmedium
5. 20.Workflow Dependency Execution
   Task DAG orchestration using ready task queuemedium
6. 21.Dependency Resolution
   System component startup orderingmedium
7. 22.Lexicographically Smallest Topological Order
   Kahn's Algorithm using Min Heap (PriorityQueue) instead of FIFO Queuemedium
8. 23.Unique Topological Ordering
   Validate queue size is strictly 1 at every step during Kahn executionmedium

How to Think

1. Need dependency order?Kahn's Algorithm (Indegree 0 Queue)
2. Need nodes that are ready now?Indegree == 0 (0 unfinished prerequisites)
3. Need detect cycle in directed graph?Kahn fails (processedCount < totalNodes)
4. Need process dependency levels / semesters?Kahn + BFS Level loop (size := len(queue))

// 1. Standard Kahn's Algorithm (BFS Queue): O(V + E) Time
func topoSortKahn(n int, edges [][]int) []int {
    adj := make([][]int, n)
    indegree := make([]int, n)

    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        indegree[v]++
    }

    queue := []int{}
    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    order := []int{}
    head := 0

    for head < len(queue) {
        u := queue[head]
        head++
        order = append(order, u)

        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v) // Unlocked!
            }
        }
    }

    if len(order) != n {
        return nil // Cycle detected!
    }
    return order
}

// 2. Parallel Courses / Semesters (Level Loop Kahn): O(V + E) Time
func minSemesters(n int, relations [][]int) int {
    adj := make([][]int, n+1)
    indegree := make([]int, n+1)

    for _, r := range relations {
        adj[r[0]] = append(adj[r[0]], r[1])
        indegree[r[1]]++
    }

    queue := []int{}
    for i := 1; i <= n; i++ {
        if indegree[i] == 0 { queue = append(queue, i) }
    }

    semesters := 0
    processed := 0

    for len(queue) > 0 {
        size := len(queue)
        semesters++
        for i := 0; i < size; i++ {
            u := queue[0]
            queue = queue[1:]
            processed++

            for _, v := range adj[u] {
                indegree[v]--
                if indegree[v] == 0 {
                    queue = append(queue, v)
                }
            }
        }
    }

    if processed != n { return -1 }
    return semesters
}

The Indegree Unlocking Rule

Parallel Execution Waves & Min Heap Topo

Kahn's Algorithm   → Indegree 0 Ready Queue for DAG topological ordering
Indegree           → Number of unfinished prerequisites pointing to node
Queue Pop          → Append to order -> Decrement neighbors' indegree
Neighbor 0         → Enqueue immediately (Unlocked!)
Cycle Check        → processedCount < n when queue empty = Dependency Deadlock!
Min Heap Variant   → Replace Queue with Min Heap for smallest numerical order

Common Interview Mistakes

Interview Rules

1. 1. Prerequisites / Dependencies?→ Kahn's Algorithm (Indegree 0 Queue)
2. 2. Indegree calculation? → Count incoming edges for each node 0..n-1
3. 3. Processing step? → Pop ready node u, append to order, decrement indegree[v]-- for all u -> v
4. 4. Neighbor unlocking? → Enqueue neighbor v immediately when indegree[v] == 0
5. 5. Dependency cycle check? → Cycle exists if processedCount < n when queue empties
6. 6. Parallel rounds / semesters? → Level-by-level queue size loop (size := len(queue))
7. 7. Smallest valid order? → Replace Queue with Min Heap (PriorityQueue)
8. 8. Overall Complexity → Time: O(V + E) | Space: O(V + E)

Kahn's Algorithm → Indegree 0 Queue

Build Graph + Calculate Indegrees
Indegree 0       → Ready Queue
Pop Ready Node   → Add to Order
For Each Neighbor→ indegree--
Becomes 0?       → Enqueue (Unlocked!)
Queue Empty      → Check processedCount == N (Cycle if < N)
Parallel Rounds  → Level loop (size := len(queue))
Smallest Order   → Min Heap (PriorityQueue)
Time             → O(V + E)

💡 Golden Rule: "Keep processing whatever has zero unfinished dependencies; each completed node may unlock the next set of ready nodes."