トポロジカルソート
ソフトウェアをインストールするとき、プログラムをビルドするとき、プロジェクトを計画するとき、いつも何かが「最初に何をするか」を決めています。作業 B に作業 A が必要なら、A を先にやらなければなりません。トポロジカルソートは、そうしたルールの網を1本の直線に変えます。
考え方
各作業をノードとして、「A は B より先」という各ルールを A から B への矢印として描きます。トポロジカル順序は、どの矢印も右を向くようにすべてのノードを1列に並べたものです。ものを順に並べるのでソートと呼ばれますが、数の並べ替えと違い、守るのは矢印だけです。矢印の連なりでつながっていないノードどうしは、どちらが先でもかまいません。
不可能なとき
矢印が閉路を作ると、たとえば A は B より先、B は C より先、C は A より先だと、A は自分より先に来なければなりません。そのため、トポロジカル順序はグラフに有向閉路がないとき、そしてそのときに限り存在します。そのようなグラフを有向非巡回グラフ(DAG)と呼びます。以下の2つの方法はどちらも、閉路があれば見つけるので、閉路の判定にも便利です。
例
矢印 A → C、B → C、B → D、C → E、D → E を考えます。カーンのアルゴリズムは入ってくる矢印を数えます。A と B には1本もないので、まず A、次に B を置きます。B の矢印を取り除くと C と D が置けるようになって続き、最後に E が来ます。順序は A, B, C, D, E です。DFS 法は A、次に C、次に E を訪問します。最初に E が終わり、次に C、次に A が終わって、それぞれ先頭に置かれます。次に B と D を訪問し、それらが終わってさらに前に置かれます。順序は B, D, A, C, E です。どちらの順序も正解です。
カーンか DFS か
1962 年に Arthur Kahn が発表したカーンのアルゴリズムは前から進みます。いま始められる作業が常にわかるのでスケジューリングに向いており、置けるノードの中からアルファベット順など好きなルールで選べます。1976 年に Robert Tarjan が広めた DFS 法は終わりから逆向きに進み、深さ優先探索だけで済みます。どちらも、かかる時間はノード数とエッジ数の和に比例して増えます。
用途
make のようなビルドツールは、ファイルが依存するファイルを先にコンパイルします。パッケージマネージャーは依存関係の順にライブラリをインストールします。表計算ソフトは、セルの数式が使うセルを先に計算してから、そのセルを再計算します。大学では履修の前提条件を満たせるかを確かめ、コンパイラーは命令を並べ、データパイプラインは入力がそろってから各ステップを実行します。Unix のコマンド tsort は、それ自体がトポロジカルソートを行います。
試してみよう
アプリを開いて「ステップ」を押してください。矢印は、どのノードがどのノードより先でなければならないかを示します。カーンのアルゴリズムでは、各ノードの数字は残っている入ってくる矢印の数で、置けるノードは青です。DFS 法では、青いノードは訪問中、緑のノードは配置済みです。順序はグラフの下の列で伸びていきます。「閉路を追加」にチェックを入れて、どちらの方法も順序がないことを見つける様子を見てみましょう。
よくある質問
ここでいう「トポロジカル」とは?
名前は位相幾何学(トポロジー)から来ています。ものの正確な形ではなく、どうつながっているかを調べる分野です。順序はどのノードが矢印でつながっているかだけで決まり、どこに描かれているかには関係ありません。
順序がないとき、閉路はどう見つける?
DFS 法ならそのまま示されます。まだ訪問中のノードへのエッジと、訪問中のノードの経路を合わせたものが閉路です。カーンのアルゴリズムは、どのノードが行き詰まったかを教えるだけです。それらの中を探索すれば閉路が見つかります。
正しい順序の中から特定の1つを選べる?
はい。カーンのアルゴリズムで置けるノードが複数あるとき、好きなものを選びます。たとえばラベルが最小のものや、最も急ぐ作業です。優先度付きキューを使えば、アルファベット順で最初に来る順序が得られます。
トポロジカルソートは最短経路にどう使われる?
有向非巡回グラフでは、トポロジカル順序で各ノードのエッジを緩和すれば、1回の走査でスタートからのすべての最短経路が求まります。負のエッジがあってもよく、ダイクストラ法やベルマン–フォード法より高速です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
トポロジカルソートを試す