Which of the following graph traversal algorithms is typically used to produce a topological ordering?

• A. Breadth-first search
• B. Depth-first search
• C. Dijkstra's algorithm
• D. Prim's algorithm

Answer: (B)

Topological ordering lists vertices so that every directed edge points from an earlier vertex to a later one. Depth-first search provides a natural way to achieve this. When you explore from a vertex, you dive deep along its successors before finishing the current vertex. You record a vertex only after all vertices reachable from it have been explored. If you collect vertices in the order they finish and then reverse that order (or push them onto a stack as they finish and pop later), you get a valid topological order. This works because for every edge u → v, v is finished before u, so reversing the finishing order places u before v as required. This approach requires the graph to be a DAG; with cycles, a topological order doesn’t exist, and DFS can help reveal a cycle if you track the recursion stack.

BFS by itself isn’t designed to enforce the dependency-based ordering required for topological sorting, while Dijkstra’s and Prim’s algorithms are about shortest paths and minimum spanning trees, not ordering.