Directed Acyclic Graphs (DAGs)

A Directed Acyclic Graph (DAG) is a directed graph with no cycles. "Directed" means edges have a direction ($A \to B$ is not the same as $B \to A$). "Acyclic" means you can never follow edges and return to where you started.

Topological sort only works on DAGs. If your graph has a cycle like $A \to B \to C \to A$, there is no valid ordering. $A$ must come before $B$, $B$ before $C$, and $C$ before $A$, which is a contradiction. Detecting whether a graph is a DAG is part of the topological sort process. If the algorithm cannot order all nodes, you know a cycle exists.