Definition
Topological Sorting
A topological sorting is a linear ordering of the vertices of a directed graph such that, for every edge , vertex appears before vertex in the ordering.
A topological sorting exists if and only if the graph is a directed acyclic graph.
Uniqueness
Uniqueness
A directed acyclic graph can have multiple valid topological orderings. If the graph contains a cycle, no topological ordering exists.
Algorithms
Source-Node Removal
Source-node removal
A standard topological sorting algorithm repeatedly removes every source vertex, that is, every vertex with in-degree .
Each removed vertex is appended to the output order. Deleting its outgoing edges may create new sources. If vertices remain but no source exists, the graph contains a cycle and no topological ordering exists.