作業フローを簡素化：miniwebtoolを検索。
追加
関連ツール
隣接行列電卓ダイクストラ最短経路電卓グラフ彩色電卓グラフ次数列バリデーター安定結婚問題ソルバー
ホームページ > 数学 > 高度な数学操作 > トポロジカルソート電卓
 

トポロジカルソート電卓

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

トポロジカルソート電卓

⚡ 例を試す:

線形チェーン 着替えの順番 履修科目の前提条件 モーニングルーティン ビルドターゲット 隣接リストのサンプル サイクルあり パイプライン DAG
エッジ形式: A -> B（→、=>、: も使用可能）。最大 80 頂点 / 800 エッジ。
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₂, …, vn) がトポロジカルであるための必要十分条件は、
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:

この電卓の使い方

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

計算量とパフォーマンス

よくある質問

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

有向非巡回グラフのトポロジカルソートとは、すべての有向エッジ 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 ベースの解析と組み合わせるのが容易です。

このツールがサポートする最大グラフサイズは？

この電卓は最大 80 頂点と 800 エッジをサポートします。有効なトポロジカル順序の総数のカウントは、問題が #P完全であり状態空間が 2ⁿ で増大するため、16 頂点に制限されています。インタラクティブな視覚化とアニメーションは、最大サイズまでスムーズに動作します。

参考文献

このコンテンツ、ページ、またはツールを引用する場合は、次のようにしてください：

"トポロジカルソート電卓"（https://MiniWebtool.com/ja/トポロジカルソート計算機/） MiniWebtool からの引用、https://MiniWebtool.com/

作成: miniwebtool チーム、更新日: 2026年4月20日

また、AI 数学ソルバー GPT を使って、自然言語による質問と回答で数学の問題を解決することもできます。

高度な数学操作:

おすすめ:

マスターナンバー電卓InstagramユーザーID検索パーセンテージ減少電卓パーセント増加電卓サッカーxg期待ゴール電卓弧長電卓パーセント誤差電卓標準偏差電卓 - 高精度ランダムカラージェネレーター合計電卓画像分割ツールシグマ記法電卓 総和動画を結合HEX電卓円錐展開図テンプレートジェネレーターMACアドレス検索番号を並べ替える中央値電卓筆算割り算電卓フィートとインチからセンチメートルへのコンバーター英単語ランダム生成ツールエンジェルナンバー電卓ランダム超能力ジェネレーター平方完成電卓ランダム絵文字ジェネレーター不可視文字除去ツール太陽位置計算機動画を逆再生war電卓逆テキスト売上総利益率電卓ランダム誕生日ジェネレーターボウリングスコア計算機ai句読点追加手数料電卓楕円円周電卓ASCIIコード表ランダムトーナメント表作成ツール加速度電卓MP3ルーパー相対標準偏差電卓FPSコンバーターCAGR電卓対数電卓モジュロ電卓ランダム名前ジェネレータービンゴカードジェネレーター動画を回転センチメートルからフィートとインチへのコンバーター変化率電卓ボルト締付トルク計算機t検定電卓相関係数計算機関数電卓階段電卓比率電卓血糖値コンバーターランダム日付ジェネレーターYouTubeチャンネル統計私のIPアドレスは何ですかHEXコンバーター圧力電卓ビデオ速度を調整fena電卓マン・ホイットニーのU検定計算機平均寿命電卓デシベル (dB) 電卓桁数電卓小数時間から普通の時間へのコンバーター🖱️ クリックカウンター外れ値電卓クロスワードパズルメーカー土星回帰電卓指数電卓-高精度平方根電卓迷路ジェネレーターオーディオ スプリッターピタゴラスの定理電卓分数電卓XMLバリデーター上下反転テキストジェネレーターBUN対クレアチニン比電卓ホームランの打席電卓熱膨張計算機SRTからTXTへの変換ツール積分電卓斜辺電卓変動係数電卓パスワード強度テスター労働時間計算ツール正多角形電卓筆算足し算・引き算計算機log-base-2電卓バイナリ電卓行番号を追加CRC32チェックサム電卓タンジェント電卓平均電卓-高精度角度変換ツールANC電卓画像回転ツール空の行を削除するトルク電卓🔊 トーンジェネレーター周波数波長変換ツールじゃんけんジェネレーター10進数からBCDへのコンバーター中国剰余定理電卓年の日電卓 - 今日は今年の何日目分散電卓 高精度VTTからtxtへのコンバーター太陽・月・上昇星座電卓 🌞🌙✨ランダム時刻ジェネレーター動画から画像抽出ツールcsvからsrtへTikTok収益計算ツールHTMLからテキストコンバータSHA256 ハッシュジェネレーター👙 ブラサイズ電卓三角関数グラフ作成ツール二乗平均平方根電卓慣性モーメント計算機水泳ペース計算機熱伝達計算機パーセント成長率電卓文字数による改行角速度計算機パーソナリティ・ナンバー電卓学習曲線電卓自然対数電卓並列抵抗電卓割り切れるテスト電卓複数分数電卓CMYKからHEXへの変換ツールコラッツ予想電卓標準誤差電卓💧 露点電卓インタラクティブ単位円ビジュアライザーベーカーズパーセント電卓車両重量配分計算機BCDからバイナリへのコンバーター配管流量電卓IPアドレスから16進数への変換パレットジェネレーターランダムクレジットカードジェネレーターワイヤーゲージ電卓絶対値不等式ソルバーピザ生地計算機eの最初のn桁Zalgoテキストジェネレーター中間日計算機平均中央値モード電卓服のサイズ変換音節カウンターpH電卓ランダムグループジェネレーター水星逆行カレンダー点つなぎジェネレーターGIFメーカーアナグラム生成器オンライン句読点削除ツールコラージュメーカービデオをループ再生カイ二乗検定電卓ランダム算数問題ジェネレーター分圧器計算電卓沸点計算ツール逆行列電卓FacebookユーザーID検索hba1c電卓エラー関数電卓梁の電卓配当利回り電卓3d距離電卓双曲線関数電卓平均電卓部分分数分解電卓10進数から16進数へのコンバーターランダムアニマルジェネレーター円錐台電卓論理ゲートシミュレーター退職カウントダウンYouTubeショート収益化計算ツールケリー基準電卓ヴァンパイア黙示録電卓⏱️ 時間計算機水分補給計算機絶対値電卓10進数からバイナリへのコンバーターAIテキストヒューマナイザーLED抵抗器電卓グレイコード・バイナリ変換電卓ノノグラムジェネレーター (ピクロス)馬力電卓テンソル積電卓ビデオ反転ピッグラテン翻訳機ランダム整数ジェネレーター二項係数電卓動画圧縮CGPAからパーセンテージへの変換器簡単採点ツール EZ Grader子育て費用計算機赤ちゃんのミルク量計算おむつサイズ電卓赤ちゃんの名前ジェネレーター赤ちゃんの目の色予測子供のBMIパーセンタイル計算機子供の身長予測ツールhcg倍加時間計算ツール体外受精出産予定日電卓着床計算ツール中国式性別予測カレンダーISO 8601 日付フォーマッターユリウス日変換器昼寝電卓月相電卓日の出＆日の入り電卓世界時計日付ローマ数字変換電卓ソブリエティ計算機ハーフバースデー計算機記念日計算機週番号計算機チップ分配計算機メールマーケティングROI電卓リード獲得単価計算機運転資本計算機限界利益計算機FIFO / LIFO 電卓安全在庫計算機発注点計算機経済的発注量EOQ電卓減価償却計算機ハンドメイド価格電卓卸売価格計算機Shopify利益計算機Amazon FBA 電卓eBay手数料計算機Etsy手数料計算機Stripe手数料計算機PayPal手数料計算機ベッティングオッズ変換器什一献金計算機ザカート計算機英国印紙税計算機HRA非課税計算ツールグラチュイティ計算機NPS計算機EPF電卓PPF計算機RD電卓SWP電卓グロスアップ計算機ローン比較電卓クレジット利用率計算ツールCDラダー電卓T-Bill米国短期国債電卓I Bond 電卓529大学積立計算機HSA電卓退職金計算機昇給計算機請求書作成ツール出張日当計算機走行距離手当計算機家賃値上げ計算機日割り家賃計算家賃適正額計算機乗り出し価格計算ツール車購入可能額計算機バイクローン計算機キャンピングカーローン計算ボートローン電卓土地ローン計算機建設ローン計算機金利のみ住宅ローン計算機バルーンローン計算機住宅ローンポイント計算機PMI電卓隔週住宅ローン返済額計算機ARM住宅ローン電卓VAローン計算機給与手取り計算機AI SQLクエリジェネレーターAI正規表現ジェネレーターAIデータ可視化ツールCSV貼り付けAIテキストトーン分析ツールAI履歴書アナライザーAI単位変換ツール自然言語AI謝罪文ジェネレーターAI 丁寧なお断り文ジェネレーターAI旅行日程ジェネレーターAI読書リストジェネレーターAIワークアウトプランジェネレーターAI献立ジェネレーターAIギフトアイデアジェネレーターAIレシピジェネレーター食材から奨学金ROI電卓大学費用計算機言語学習 流暢になるまでの学習時間電卓単語クイズ作成ツールコーネルノート作成ツールフラッシュカード間隔反復スケジューラーペイント色混合計算機タイル目地計算機食洗機の積み込み最適化ツール洗剤の使用量計算ヘアカラー混合計算機印刷コスト計算機ガス vs 電気 コスト比較電卓ギフトカードチップ電卓引っ越し用ダンボール数計算機ストレージユニットサイズ計算機カプセルワードローブ計算機ベルト長さ計算機油圧シリンダー推力計算機滑車システム計算機ギア比計算機機械比熱計算機ベルヌーイの式計算機レイノルズ数計算機潮汐時刻計算機星空観測条件計算機結び方リファレンスツール寝袋温度評価ガイドテントフットプリントサイズ電卓バックパッキング食料重量電卓ネイスミス式ハイキングペース電卓刺繍糸長さ電卓レジンキャスト量計算電卓ビーズパターン電卓陶芸粘土収縮率電卓折り紙用紙サイズ電卓キルトバインディング電卓クロスステッチ刺繍糸計算編み物パターン計算機編み針サイズ変換器かぎ針サイズ変換器馬の干し草計算ツールペット航空輸送クレートサイズ検索爬虫類飼育UVBライト距離計算機鳥かごサイズ計算機水槽ヒーターワット数電卓猫のトイレ数計算機ヘッドライト照射距離電卓エンジン圧縮比計算機タイヤ溝摩耗計算機トレーラー牽引荷重計算機旅行費用割り勘計算停止距離計算機労災補償計算機遺産配分電卓商標区分検索ツール特許出願料電卓売上税ネクサスチェッカー刑期短縮計算機時効計算機Airbnb料金最適化ツールルームメイト家賃分割計算機セクション8 家賃電卓BRRRR法計算機キャッシュオンキャッシュリターン計算機賃貸利回り計算機1031エクスチェンジ計算機資産成長ビジュアライザーランチ代計算機ジム vs 自宅トレーニング費用電卓コーヒー代計算機リモートワーク節約計算機副業ROI電卓サブスクリプション費用トラッカーSaaS料金計算ツールフリーランスプロジェクト料金計算機スモークウッド・ペアリングガイド発酵時間計算機マリネ時間計算機食事制限レシピフィルタースパイス代用品ファインダーカフェイン半減期トラッカー標準ドリンク計算ツールワインペアリング提案ツールクライミンググレード変換器自転車ギア比計算機釣り結び強度計算機ヨガポーズホールドタイマー水泳SWOLF電卓レースタイム予測計算機ボクシングパンチ力計算機ラグビー得点電卓クリケット・ランレート電卓テニススコアトラッカーWellsスコア電卓 (DVT/PE)グラスゴー・コーマ・スケール計算機アプガースコア計算機FFMI 電卓クーパー12分間走計算ツール1マイルウォークテストロックポート電卓除脂肪体重から筋力計算炭水化物インスリン比計算機インスリン感受性係数計算機ヘブライ暦変換器ヒジュラ暦変換器旧暦変換ツール文化別年齢電卓どれくらい前計算機あと何日カウントダウン電卓日付パターンジェネレーター日付に営業日を追加営業日計算機単語頻度アナライザー文の長さばらつき分析ツールヘミングウェイ風リーダビリティエディタ発音IPA変換ツールヴィジュネル暗号ツールアトバッシュ暗号ツールROT13エンコーダー・デコーダーEXIFデータビューア・削除ツールバックロニム ジェネレーター頭字語ジェネレーターパングラムチェッカーリポグラム チェッカー画像からSVGトレーサー画像からASCIIアートへの変換器JSONスキーマジェネレーターTypeScriptプレイグラウンドLessからCSSへのコンパイラーSCSSからCSSへのコンパイラーSVGからReact/JSXへの変換器クエリ文字列ビルダーURLパーサーUUID検証・デコーダーHTTPステータスコードリファレンスcURLコマンドビルダーシェルピンスキーの三角形ジェネレーター3D曲面プロッター極方程式プロッタージュリア集合生成器マンデルブロ集合エクスプローラーL-Systemフラクタルジェネレータードロネー三角形分割ジェネレーターボロノイ図ジェネレータースピログラフジェネレーターテッセレーションジェネレーターシックスシグマ工程能力計算機youtubeサムネイルダウンローダーyoutube収益見積もりツールランダムRPGキャラクタージェネレーター