トポロジカルソートとは？
とぽろじかるそーと
トポロジカルソートとは、有向非巡回グラフ（DAG）において、すべての辺の向きに従う順序でノードを一列に並べるアルゴリズムです。
トポロジカルソートとは、有向非巡回グラフ（DAG: Directed Acyclic Graph）のすべてのノード（頂点）を、辺の向き（依存関係）に矛盾しない線形順序に並べる操作です。あるノードAからノードBへの辺があるとき、Aは必ずBより前に並ぶように整列します。
実装方法として代表的なものに以下の2種類があります。
- カーンのアルゴリズム：入次数（in-degree）が0のノードをキューに入れ、順次取り出しながら隣接ノードの入次数を減らしていく幅優先探索ベースの方法。
- 深さ優先探索（DFS）ベース：DFSで各ノードを再帰的に訪問し、後退する際にスタックへ積み上げ、最後にスタックを逆順に取り出す方法。
グラフに閉路（サイクル）が存在する場合、トポロジカルソートは不可能です。アルゴリズムの実行中にサイクルの存在を検出することもできます。計算量はノード数をV、辺数をEとするとO(V+E)です。
トポロジカルソートは実際のソフトウェア開発で広く使われています。代表的な用途としては、ビルドシステムでのコンパイル順序決定、パッケージ管理システムでの依存関係解決、タスクスケジューリングなどがあります。
使い方・例文
たとえば「CをコンパイルするにはまずライブラリBが必要で、BにはライブラリAが必要」という依存関係をDAGで表現し、トポロジカルソートを適用することで正しいビルド順序（A→B→C）を自動的に求められます。
この用語をシェア
最終更新: