Beyond basic traversal, graphs solve specific real-world architectural problems. From determining the order of compile tasks to finding fake accounts, these algorithms are the engine of modern software.

Topological Sorting

Used for scheduling and dependency resolution. In a Directed Acyclic Graph (DAG), it provides a linear ordering of vertices such that for every directed edge uv, vertex u comes before v.

Interview Hack: Kahn's Algorithm

The most intuitive way is to find nodes with In-Degree 0 (no dependencies), add them to your result, and "remove" them to reveal new nodes with 0 In-Degree.

LINEAR ORDER: DATA → AUTH → PARSER → MAIN UI

Pseudocode

1// Kahn's Algorithm (Topological Sort)
2function topologicalSort(numNodes, edges) {
3  const adj = Array.from({ length: numNodes }, () => []);
4  const inDegree = new Array(numNodes).fill(0);
5 
6  for (const [u, v] of edges) {
7    adj[u].push(v);
8    inDegree[v]++;
9  }
10 
11  const queue = [];
12  for (let i = 0; i < numNodes; i++) {
13    if (inDegree[i] === 0) queue.push(i);
14  }
15 
16  const order = [];
17  while (queue.length) {
18    const u = queue.shift();
19    order.push(u);
20 
21    for (const v of adj[u]) {
22      inDegree[v]--;
23      if (inDegree[v] === 0) queue.push(v);
24    }
25  }
26 
27  return order.length === numNodes ? order : [];
28}