complexitygraphsqueues
A topological order needs a directed acyclic graph
Anonymous
For a directed graph, Kahn's algorithm starts with vertices of indegree zero, then removes one at a time and reduces the indegree of each outgoing neighbor. If the processed count is smaller than the vertex count, a directed cycle remains. When multiple vertices have indegree zero, several valid orders may exist. With adjacency lists, the scan takes O(V + E) time.
0