Topological sorting

A topological sorting is a linear ordering of a directed acyclic graph’s vertices in which every edge points from an earlier vertex to a later one.

Kahn's algorithm: A graph algorithm that repeatedly removes vertices with no incoming edges and outputs them in order. It builds a topological ordering by selecting currently unconstrained vertices.
Task scheduling: The assignment of tasks to times or resources while respecting constraints. A topological order gives a feasible sequence when tasks have prerequisite dependencies.
Directed graph: A graph whose edges have specified directions from one vertex to another. Topological sorting orders vertices according to these directed edges.
Topological uniqueness: The property that a directed acyclic graph has exactly one topological ordering. A unique order occurs precisely when each consecutive choice is forced.
Depth-first search: A graph traversal that explores each vertex’s outgoing paths before backtracking. Reversing its finishing order yields a topological sort of a DAG.
Build system: Software that automates compiling and assembling projects from source files and dependencies. Build tools order dependent targets so prerequisites are produced first.
Directed acyclic graph: A directed graph containing no directed cycle. Only graphs without directed cycles admit a topological ordering.
Stable topological sort: A topological ordering that preserves a chosen relative order among otherwise incomparable vertices. It adds a tie-breaking preference without violating edge constraints.
Indegree: The number of edges directed into a vertex in a graph. Kahn’s algorithm selects vertices whose indegree has fallen to zero.
Package manager: Software that installs, upgrades, and removes packages while managing their dependencies. Installation plans use dependency order to ensure required packages arrive first.

Linked from 13 pages