An ordering of the vertices of a directed acyclic graph such that every edge points from an earlier vertex in the ordering to a later one, used to schedule tasks with dependencies such as a build system or a course prerequisite chain.
Facts
Core PrincipleOrders the vertices of a directed acyclic graph into a sequence so that every edge runs from an earlier vertex to a later one, giving a valid processing order for tasks with dependencies. 1 Connections
In Field
Invented
Robert Tarjan published a linear-time topological sort algorithm using depth-first search in his 1976 paper Edge-disjoint spanning trees and depth-first search, following Arthur Kahn's earlier 1962 algorithm.
Sources
1. Wikipedia: Topological Sort
Wikimedia FoundationKahn's algorithm section, first sentence
first described by Kahn (1962)
Lead section, first sentence
a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.