Which algorithmic approaches can produce a topological order for a directed acyclic graph?

• A. DFS-based finishing times
• B. Kahn's algorithm
• C. Both DFS-based finishing times and Kahn's algorithm
• D. Neither method works

Answer: (C)

Topological order means arranging vertices so every edge goes from an earlier to a later vertex. Two classic procedures guarantee this for a directed acyclic graph. With a DFS-based finish-time approach, you finish a vertex only after all vertices reachable from it are finished. So for any edge u → v, v finishes before u, and when you output in reverse finishing order, u appears before v, satisfying the dependency. Kahn's algorithm uses in-degrees: repeatedly remove a vertex with zero in-degree and append it to the order, reducing the in-degrees of its neighbors. This ensures you never place a vertex before any of its prerequisites, and in a DAG you eventually remove all vertices, yielding a valid topological order. Hence, both methods can produce a topological order.