Which algorithm processes a directed acyclic graph by repeatedly removing a node with zero in-degree and updating its neighbors?

• A. DFS-based finishing times
• B. Kahn's algorithm
• C. Bellman-Ford
• D. Dijkstra

Answer: (B)

Topological sorting by removing a node with zero in-degree and updating its neighbors is a queue-based method for ordering the nodes of a DAG. The idea is simple: a node with no prerequisites can come first, and when you “remove” it, you decrease the in-degree of its successors. If any of those neighbors then has zero in-degree, it becomes eligible to be placed next. Repeating this process builds a valid linear ordering of the graph. If you ever reach a point where no node has zero in-degree but unprocessed nodes remain, the graph contains a cycle.

This approach is Kahn's algorithm, which explicitly uses in-degree counts and a queue to produce a topological order. It’s distinct from DFS-based methods, which produce a topological order via the finishing times of a depth-first search rather than by repeatedly stripping zero in-degree nodes. It’s also unrelated to shortest-path algorithms like Bellman-Ford or Dijkstra, which explore paths and relax edge weights rather than constructing a topological ordering.