What signals in a problem statement indicate the Kahn's algorithm (BFS) sub-pattern?

"return the ordering of courses / tasks"; "minimum number of semesters" / "minimum time" with parallel work; "roots of minimum height trees" (peel leaves layer by layer)

Kahn's algorithm (BFS) (Topological Sort Sub-pattern)

Q: What makes Kahn's algorithm (BFS) different from other sub-patterns?

**Topological Sort** and **Course Schedule II** are the template (mind the `[a, b]` = b → a direction). **Parallel Courses** counts Kahn **rounds**: each round is one semester. **Parallel Courses III** carries a finish time along each edge: `finish[v] = max(finish[u]) + time[v]`. **Minimum Height Trees** runs the same peeling on an undirected tree with **degree 1** instead of in-degree 0, stopping when ≤ 2 nodes remain.

Produce an order (or a schedule) where every prerequisite comes first.

Signals in the problem statement

›
"return the ordering of courses / tasks"
›
"minimum number of semesters" / "minimum time" with parallel work
›
"roots of minimum height trees" (peel leaves layer by layer)

What makes it different

Topological Sort and Course Schedule II are the template (mind the [a, b] = b → a direction). Parallel Courses counts Kahn rounds: each round is one semester. Parallel Courses III carries a finish time along each edge: finish[v] = max(finish[u]) + time[v]. Minimum Height Trees runs the same peeling on an undirected tree with degree 1 instead of in-degree 0, stopping when ≤ 2 nodes remain.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Topological Sort (template)
Basic Anchor·GeeksforGeeks
WalkthroughEasy
2
Course Schedule II
Basic Reinforcement·LeetCode #210
WalkthroughMedium
3
Parallel Courses
Slight Variation·LeetCode #1136 Premium
WalkthroughMedium
4
Parallel Courses III
Medium·LeetCode #2050
WalkthroughHard
5
Minimum Height Trees
Pattern Transfer·LeetCode #310
WalkthroughMedium

Template

kahn-template.cpp

// Kahn's algorithm: repeatedly take a node nothing points to any more.
vector<int> topoSort(int n, const vector<vector<int>>& edges) {   // edge {u, v} = u must come before v
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }
    queue<int> q;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);                       // everything before u is already placed
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);       // v's last prerequisite just got placed
    }
    if ((int)order.size() < n) return {};         // some nodes never reached in-degree 0: a cycle
    return order;
}

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Topological Sort overview Cycle detection / feasibility