トポロジカルソートとは？
トポロジカルソートとは、「AはBより先」という順序制約を辺で表した有向非巡回グラフ（DAG）に対し、すべての制約を満たす一列の順序を求める処理。入次数0の頂点から取り出して辺を除去する手順を繰り返すか、深さ優先探索の帰りがけ順の逆順で求める。
とぽろじかるそーと
トポロジカルソートの意味
「AはBより先」という順序制約を辺で表した有向非巡回グラフ（DAG）に対し、すべての制約を満たす一列の順序を求める処理。入次数0の頂点から取り出して辺を除去する手順を繰り返すか、深さ優先探索の帰りがけ順の逆順で求める。
トポロジカルソートの具体例
ビルドツールが依存関係からコンパイル順を決める処理、表計算の再計算順の決定、履修の前提科目からの受講順の作成などが典型。プロジェクトの先行関係から作業順を並べるアローダイアグラムの考え方とも通じる。
トポロジカルソートは試験でどう引っ掛けられる？
閉路があると順序を作れず、途中で入次数0の頂点が尽きる。この性質を使って循環依存の検出そのものに応用できる。また解は一般に一意ではなく、複数の正しい順序が存在する点も問われやすい。
トポロジカルソートと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。