Topological sort

GPTKB entity

Statements (18)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:appliesTo gptkb:directed_acyclic_graph
gptkbp:category graph algorithms
gptkbp:common_algorithm gptkb:Depth-first_search
Kahn's algorithm
gptkbp:complexity O(V+E)
gptkbp:describedYear 1962
gptkbp:firstDescribed Arthur H. Kahn
https://www.w3.org/2000/01/rdf-schema#label Topological sort
gptkbp:not_possible_for graphs with cycles
gptkbp:output linear ordering of vertices
gptkbp:used_in scheduling
dependency resolution
build systems
course prerequisite analysis
gptkbp:usedFor ordering vertices of a directed acyclic graph
gptkbp:bfsParent gptkb:Boost.Graph
gptkbp:bfsLayer 6