topological-sort.md

← Return to Index

Topological Sort

In a Directed Acyclic Graph, vertices have a 'partial' order:

• if A → B, then A < B. If A → B → C
• then we know that A < B, B < C
• and therefore, A < C

A Topological Sort is a list of the vertices in partial order.

Bonus: here's a real-life example of a DAG in use.