Intermediate LevelData Structures & Algorithms
What is Topological Sorting and how does Kahn's Algorithm work?
ā Interview Prompt: Explain Topological Sort, DAG prerequisite, Kahn's BFS algorithm using in-degrees, cycle detection, and use cases.
Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that every edge $u \to v$ places $u$ before $v$.
Kahn's Algorithm (BFS-based):
1
Compute in-degree of every vertex (number of incoming edges).
2
Enqueue all vertices with in-degree = 0 (no dependencies).
3
While queue is non-empty:
ā¢
Dequeue vertex $u$; add to result.
ā¢
For each neighbour $v$ of $u$: decrement in-degree of $v$. If it becomes 0 ā enqueue $v$.
4
If result contains all $V$ vertices ā valid topological order. Else ā cycle exists.
ā¢
Time: $O(V + E)$, Space: $O(V)$.
Code Implementation Example
typescript
function topoSort(numCourses: number, prerequisites: number[][]): number[] {
const inDeg = new Array(numCourses).fill(0);
const adj: number[][] = Array.from({ length: numCourses }, () => []);
for (const [course, pre] of prerequisites) {
adj[pre].push(course);
inDeg[course]++;
}
const queue = inDeg.map((d, i) => d === 0 ? i : -1).filter(i => i >= 0);
const order: number[] = [];
while (queue.length) {
const u = queue.shift()!;
order.push(u);
for (const v of adj[u]) {
if (--inDeg[v] === 0) queue.push(v);
}
}
return order.length === numCourses ? order : []; // [] if cycle
}š”Kahn's BFS topological sort with cycle detection.
šÆ Interview Key Takeaway
Topological sort only works on DAGs. Use Kahn's for BFS-style (detects cycles naturally) or DFS postorder for recursive solutions.
#DSA#Topological Sort#Graph#Kahn#Intermediate
Back to all Data Structures & Algorithms Questionsā