トポロジカルソート電卓

KahnのアルゴリズムまたはDFSを使用して、有向非巡回グラフ（DAG）のトポロジカル順序を計算します。閉路の検出、閉路パスの報告、並列実行レイヤービューの構築、辞書順最小の並べ替えをサポートし、インタラクティブなグラフ上で各ステップをアニメーション表示します。

トポロジカルソート電卓

⚡ 例を試す:

線形チェーン着替えの順番履修科目の前提条件モーニングルーティンビルドターゲット隣接リストのサンプルサイクルありパイプライン DAG

入力形式

→ 隣接リスト

⧇ 隣接リスト

グラフデータ

エッジ形式: A -> B（→、=>、: も使用可能）。最大 80 頂点 / 800 エッジ。

隣接形式: A: B, C, D — 1行に1つの頂点と、その直後の後続ノードを記述。

アルゴリズム

Kahnアルゴリズム（辞書順）は、一意で再現可能な順序を返します。DFSポストオーダーは古典的な深さ優先手法です。

Embed トポロジカルソート電卓 Widget

トポロジカルソート電卓

トポロジカルソート計算機は、すべての有向エッジ u から v について u が v よりも前に位置するような、有向非巡回グラフ (DAG) の頂点の線形順序を計算します。グラフをエッジリストまたは隣接リストとして入力すると、KahnアルゴリズムまたはDFSポストオーダーを使用してトポロジカル順序を返し、サイクル検出（正確なサイクルパス付き）、タスクの並列実行レイヤーへのグループ化、有効な順序の数のカウント、およびインタラクティブなグラフ上での各ステップのアニメーション表示を行います。

トポロジカルソートとは何ですか？

有向グラフ G = (V, E) が与えられたとき、トポロジカルソート（またはトポロジカル順序）とは、すべての有向エッジ (u → v) について、配置内で u が v よりも前に現れるような頂点の線形配列 v₁, v₂, …, vₙ です。トポロジカル順序は、グラフに有向サイクルがない場合、つまりグラフが DAG である場合にのみ存在します。この順序は一意であることは稀で、複数の頂点の入次数が同時にゼロになる場合、多くの有効なトポロジカルソートが存在し得ます。

トポロジカル順序の定義

V の置換 (v₁, v₂, …, v_n) がトポロジカルであるための必要十分条件は、
E 内のすべてのエッジ (u → v) について: position(u) < position(v) であること

この電卓で使用されているアルゴリズム

Kahnアルゴリズム（BFSベース、1962年）

Kahnアルゴリズムは、最も直感的なトポロジカルソートです。各ステップで入次数がゼロ（入ってくるエッジがない）の頂点を選択し、それを出力に追加し、その後続ノードの入次数を減らすことでグラフからその頂点を「削除」します。複数の頂点の入次数がゼロの場合、タイブレーク（同順位の解消）には、最小ヒープ（辞書順で最小の順序が得られる）または FIFO キュー（挿入順が得られる）を使用できます。Kahnアルゴリズムは O(|V| + |E|) 時間で実行され、サイクル検出器としても機能します。キューが空になった後も入次数が 0 より大きい頂点が残っている場合、そのグラフにはサイクルがあります。

Kahnアルゴリズム（擬似コード）

Kahn(G):
  Q ← { v ∈ V : indeg(v) = 0 }
  L ← [ ]
  while Q が空でない:
    u ← Q.pop()
    L.append(u)
    for 各エッジ u → v:
      indeg(v) -= 1
      if indeg(v) = 0: Q.push(v)
  if |L| < |V|: サイクルを報告
  else: L を返す

DFSポストオーダー（Tarjan、1976年）

DFSアルゴリズムは深さ優先探索を実行し、頂点の探索が終了（つまり、その後続ノードがすべて完全に探索された）するたびに、その頂点をスタックにプッシュします。最後にスタックを反転させると、有効なトポロジカル順序が得られます。サイクル検出も自然に行えます。探索が進行中（GRAY とマーク）の頂点に遭遇した場合は、後退エッジが見つかったことを意味し、そのグラフは DAG ではありません。DFSポストオーダーも O(|V| + |E|) 時間で実行されます。

DFSポストオーダー（擬似コード）

DFS-Topo(G):
  for 各頂点 u in V: color[u] ← WHITE
  L ← 空のスタック
  for 各頂点 u in V:
    if color[u] = WHITE: visit(u)
  return reverse(L)

visit(u):
  color[u] ← GRAY
  for 各エッジ u → v:
    if color[v] = GRAY: サイクルを報告
    if color[v] = WHITE: visit(v)
  color[u] ← BLACK; L.push(u)

並列実行レイヤー

DAG の階層（レイヤー）表示は、すべてのエッジが低い番号のレベルから高い番号のレベルへ向かうように頂点を分割します。同じレイヤー内の頂点は互いに独立しているため、並列に実行できます。レイヤーの数は最長パスの長さに 1 を加えたものに等しくなります。これは DAG のクリティカルパスであり、無制限の並列処理が可能であっても、すべてのタスクを完了するために必要な最小の逐次ラウンド数です。この電卓は、入力が DAG である場合にレイヤー表示を自動的に生成します。

サイクル検出

グラフに有向サイクルが含まれている場合、トポロジカルソートは不可能です。当電卓は正確なサイクルパス（例: A → B → C → A）を報告し、視覚化上でサイクルのエッジを赤くハイライトします。サイクル上の単一のエッジを削除するだけで、非巡回性を回復できます。

入力形式

エッジリスト

各有向エッジを ソース -> ターゲット の形式で記述し、カンマまたは改行で区切ります。使用可能な矢印のバリエーション: ->, →, =>, -->, :。エッジを連鎖させることもできます。A -> B -> C は A->B と B->C の短縮形です。頂点ラベルには、文字、数字、アンダースコア、ダッシュ、ドットを使用できます。

A -> B, B -> C, A -> C
C -> D
Shirt -> Tie -> Jacket

隣接リスト

各頂点、コロン、そしてその直接の後続ノード（その頂点が指している頂点）を記述します。後続ノードがない頂点も、D: のように行を記述する必要があります。

A: B, C
B: D
C: D
D:

この電卓の使い方

形式を選択する: ラジオボタンでエッジリストと隣接リストを切り替えます。
グラフを入力する: データを貼り付けるか、クイックサンプル（着替えの順序、履修科目の前提条件、ビルドターゲット、サイクルありのグラフなど）のいずれかをクリックします。
アルゴリズムを選択する: 一意で再現可能な順序には Kahn の辞書順、入力順を保持するには挿入順、古典的な深さ優先手法には DFS ポストオーダー、または「すべて表示」で各順序を並べて確認します。
「トポロジカルソートを実行」をクリック: 順序、サイクル検出、レイヤー表示、クリティカルパス長、有効な順序の総数、およびインタラクティブなグラフが下に表示されます。
探索する: 再生ボタンを押すと、各頂点が出力されるステップを1つずつ確認できます。入次数バッジはリアルタイムで更新されます。ノードをドラッグしてレイアウトを自由に調整できます。

実世界での応用

ビルドシステムとコンパイラ

make、Bazel、Gradle、npm などのツールは、各ターゲットがすべての依存関係の後にコンパイルされるように、ビルドターゲットをトポロジカルソートします。依存関係グラフのサイクルは通常、致命的なエラーとして報告されます。ビルドシステムがどこから開始すべきか判断できないためです。

タスクスケジューリング

プロジェクトマネージャーは、タスクの依存関係を把握するために DAG を使用します。トポロジカルソートは有効な実行順序を提供し、レイヤー表示は無制限の並列処理下での最小ラウンド数を示します。最長のチェーンは、プロジェクトの期間を決定するクリティカルパスです。

履修科目の前提条件計画

大学のコースカタログは DAG です。エッジは前提条件の関係を表します。トポロジカル順序は有効な学習計画となり、レイヤーは各学期中にどの科目のセットを並行して履修できるかを学生に示します。

スプレッドシートの再計算

セルが変更されると、スプレッドシートはすべての下流のセルを依存関係順に再計算する必要があります。これはセル依存関係 DAG のトポロジカルソートです。循環参照（サイクル）はアプリケーションによって拒否されます。

パッケージマネージャーとプラグインローダー

Apt、pip、Homebrew、Maven、および無数のプラグインフレームワークは、依存関係 DAG をトポロジカルソートすることで、インストールまたはロードの順序を解決します。

シンボル解決とインストラクションスケジューリング

コンパイラは宣言を順序付けるためにトポロジカルソートを使用し、CPU はデータ依存関係に違反せずに命令をリオーダバッファにスケジュールするためにデータ依存 DAG を使用します。

トポロジカル順序のカウント

n 個の頂点を持つ DAG の場合、個別の有効なトポロジカル順序の数は、1（完全に順序付けられたチェーンの場合）から n!（エッジのないグラフの場合）の範囲になります。正確な数を計算することは一般に #P完全 な問題ですが、16 頂点までのグラフについては、この電卓はビットマスク動的計画法（f(S) = Σ f(S ∪ {v})、ここで v ∉ S かつ v のすべての前任ノードが S に含まれる）を用いて列挙します。

計算量とパフォーマンス

時間: KahnアルゴリズムとDFSポストオーダーはどちらも O(|V| + |E|) で実行され、グラフのサイズに対して線形です。
空間: 入次数の追跡と出力順序のために O(|V|)、隣接構造のために O(|V| + |E|) を使用します。
サイクル検出: 両方のアルゴリズムに組み込まれています。Kahn は |出力| < |V| のときにサイクルを検出し、DFS は後退エッジ（GRAY の隣接ノード）が見つかったときに検出します。
このツールの制限: インタラクティブな視覚化では最大 80 頂点および 800 エッジまで対応しています。順序のカウントは、頂点 16 個までとなります。

よくある質問

トポロジカルソートとは何ですか？

有向非巡回グラフのトポロジカルソートとは、すべての有向エッジ u から v について u が v よりも前に位置するように頂点を並べた線形順序です。これは、依存関係を尊重してタスクを処理する有効な順序を表します。

この電卓はどのアルゴリズムを使用していますか？

この電卓はKahnアルゴリズムとDFSポストオーダーの両方を実行します。Kahnアルゴリズムは、入次数がゼロの頂点を繰り返し削除し、その後続ノードの入次数を減らします。DFSポストオーダーは深さ優先探索を実行し、終了順序を反転させます。どちらも O(|V| + |E|) 時間で動作します。

グラフにサイクルがある場合はどうなりますか？

有向サイクルを持つグラフにはトポロジカルソートが存在しません。電卓はサイクルを検出し、視覚化の中で赤くハイライトし、正確なサイクルパスを報告するため、どのエッジを削除すればグラフを DAG にできるかを確認できます。

辞書順で最小のトポロジカル順序とは何ですか？

複数のトポロジカル順序が有効な場合、各ステップで入次数がゼロの頂点のうち、常にアルファベット順で最小のものを選択することで、辞書順で最小の順序が得られます。この電卓のデフォルトの Kahn モードはこの一意の順序を返します。

レイヤーまたはレベル表示とは何ですか？

レイヤー表示は、ソースからの最長パス長によって頂点をグループ化します。同じレイヤー内の頂点間には依存関係がないため、並列に実行できます。レイヤー数は最長依存チェーンに1を加えたものになります。

グラフに有効なトポロジカル順序が複数存在することはありますか？

はい。Kahnアルゴリズムの任意のステップで入次数がゼロの頂点が複数ある場合、そのどれを次に選んでも構いません。この電卓は、最大 16 頂点までのグラフについて、個別のトポロジカル順序の正確な数をカウントします。

KahnアルゴリズムとDFSポストオーダーの違いは何ですか？

Kahn はトップダウン方式です。繰り返しソース（入次数 0）を選択し、それらを最初に出力します。DFS ポストオーダーはボトムアップ方式です。シンク（出次数 0）を先に完了させ、それらを順序の先頭に追加していきます。どちらも O(|V| + |E|) であり、有効なトポロジカル順序を生成しますが、通常は異なる結果になります。Kahn は並列化や辞書順への対応が容易であり、DFS は強連結成分などの他の DFS ベースの解析と組み合わせるのが容易です。