トポロジカルソート
DAGのノードを、すべての辺 u→v について u が v より前に来るよう一列に並べること。要は「依存されるものが先」。
古典的なアルゴリズムは二つある。入次数0のノードを一つずつ取り除くカーンのアルゴリズムと、DFSの帰りがけ順を逆にする方法だ。どちらも計算量は O(V+E)。グラフに閉路があればトポロジカルソートは存在しない。
用途は広い。ビルドシステム（Make、Bazelでどのファイルをどの順に作るか）、パッケージマネージャ（npm、aptのインストール順）、タスクスケジューラ（Airflow、Dagster）、履修科目の前提チェック、コンパイラの命令スケジューリングなどで使われている。