Graph: Topological Sort - rFronteddu/general_wiki GitHub Wiki

In a Directed Acyclic Graph (DAG), a topological sort is a linear ordering of vertices such that for every directed edge (u,v), vertex u appears before v. This ordering is only possible if the graph has no cycles.

DFS can be used to achieve a topological sort by exploring the graph and recording the finishing times of each vertex. The vertices are then ordered by their finishing times in descending order.

topologicalSort(G)
    DFS(G) to compute finishing times v.f for each vertex
    as each vertex finishes, insert it at the front of a linked list
    return the linked list of vertices as the topologically sorted order.