作業フローを簡素化：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日

開発者向け API が利用できます: このツールをアプリ、自動化、エージェントから 1 回の JSON HTTP リクエストで実行できます。 API ドキュメントを見る

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

高度な数学操作:

おすすめ:

InstagramユーザーID検索パーセンテージ減少電卓パーセント増加電卓弧長電卓ランダムカラージェネレーターwar電卓動画を結合MACアドレス検索画像分割ツールフィートとインチからセンチメートルへのコンバーター標準偏差電卓 - 高精度円錐展開図テンプレートジェネレーターエンジェルナンバー電卓ランダム誕生日ジェネレーター番号を並べ替える引用検索 (英語)動画を逆再生ランダム日付ジェネレーターランダムポーカーハンドジェネレーター合計電卓シグマ記法電卓 総和FPSコンバーターランダム超能力ジェネレーターパーセント誤差電卓平方完成電卓売上総利益率電卓相対標準偏差電卓YouTubeチャンネル統計モジュロ電卓英単語ランダム生成ツールランダムトーナメント表作成ツール外れ値電卓熱膨張計算機HEX電卓ASCIIコード表血糖値コンバーター動画を回転オンライン句読点削除ツールMP3ルーパーデシベル (dB) 電卓逆テキスト中央値電卓マスターナンバー電卓ai句読点追加kva計算機楕円円周電卓手数料電卓センチメートルからフィートとインチへのコンバーターボウリングスコア計算機表面積電卓CAGR電卓太陽位置計算機空の行を削除する労働時間計算ツール圧力電卓🖱️ クリックカウンターマン・ホイットニーのU検定計算機ビデオ速度を調整小数時間から普通の時間へのコンバーター筆算足し算・引き算計算機ボルト締付トルク計算機ビンゴカードジェネレーターt検定電卓比率電卓コラージュメーカー桁数電卓筆算割り算電卓四分位範囲電卓私のIPアドレスは何ですかHEXコンバーター中間日計算機加速度電卓土星回帰電卓ポアソン分布電卓配管流量電卓パーセント成長率電卓変化率電卓求人検索ランダムクレジットカードジェネレーター不可視文字除去ツール熱伝達計算機パレットジェネレーターランダム絵文字ジェネレーターオーディオ スプリッター画像回転ツール関数電卓TikTok収益計算ツール愛の相性電卓SRT 時間シフト 電卓指数電卓（高精度）斜面計算機身長パーセンタイル電卓動画から画像抽出ツール配当利回り電卓散布図作成ツールSHA256 ハッシュジェネレーター年の日電卓 - 今日は今年の何日目Twitch収益計算ツール正多角形電卓車両重量配分計算機週番号計算機底2の対数電卓パーセントからppmへのコンバーター分数電卓アンテナ長計算機階段電卓XMLバリデーター世界時計atan2電卓相関係数計算機ANC電卓CRC32チェックサム電卓fena電卓BUN対クレアチニン比電卓GIFメーカーヒストグラムメーカーサイコロローラータンジェント電卓飛行距離電卓ランダムトランプカードジェネレーター角度変換ツールジニ係数電卓平方根電卓CMYKからHEXへの変換ツール動画分割ツール小文字生成器 ⁽ᶜᵒᵖʸ ⁿ ᵖᵃˢᵗᵉ⁾沸点計算ツールAIテキストヒューマナイザーアナグラム生成器ランダム名前ジェネレーターFacebookユーザーID検索カラースキームジェネレータークロスワードパズルメーカーワイヤーゲージ電卓対数電卓💧 露点電卓PSIからbarへの変換器クーパー12分間走計算ツールサッカーxg期待ゴール電卓バーコードジェネレーターローマ数字のコンバーター三相電力計算機取り消し線テキスト生成ツールトルク電卓ランニングペース電卓三角関数グラフ作成ツール割り切れるテスト電卓周波数波長変換ツール直線の方程式電卓角速度計算機じゃんけんジェネレータービデオをループ再生ランダム時刻ジェネレーター服のサイズ変換猫カロリー電卓ベーカーズパーセント電卓SRTからTXTへの変換ツール動画圧縮積分電卓迷路ジェネレーターBCD?????psiからkPaへのコンバーターそろばんシミュレーター文字数による改行日割り家賃計算魔方陣ジェネレーター🔊 トーンジェネレーター点つなぎジェネレーターhba1c電卓タイル目地計算機バイナリ電卓平均寿命電卓ポンドからキログラム変換分圧器計算電卓素数ですかカレンダー電卓hcg倍加時間計算ツール変動係数電卓水星逆行カレンダー自転車サイズ電卓IPアドレスから16進数への変換慣性モーメント計算機斜辺電卓AIお礼状ジェネレーターダイスロール確率電卓ペース カロリー電卓分散電卓 高精度直角三角形電卓10進数から16進数へのコンバーターHTMLからテキストコンバータmcgからmgへの変換ツールVTTからtxtへのコンバーターボロノイ図ジェネレーターヴィジュネル暗号ツール外接円電卓平方数リスト直列抵抗計算機グロスアップ計算機ジェスチャーゲームジェネレーターレシピ栄養計算ツールTwitter (X)用動画変換ゲーマータグジェネレーターチーム名ジェネレーターニックネームジェネレーターラップネームジェネレーターバンド名ジェネレーターファンタジー名前ジェネレーターフォーチュンクッキージェネレーターお絵描きアイデアジェネレータージャーナルプロンプトジェネレーターデイリーアファメーションジェネレーター褒め言葉ジェネレーター口説き文句ジェネレーター親父ギャグジェネレーターランダムジョークジェネレーターランダム雑学ジェネレータートリビアクイズジェネレーターハングマン単語ジェネレーターピクショナリー単語ジェネレーターアイスブレイク質問ジェネレーターNever Have I Ever ジェネレーターどっちを選ぶジェネレーターランダム質問ジェネレーターAI夢占いAI結婚式スピーチジェネレーターAIプレスリリースジェネレーターAI商品説明ジェネレーターAI動画スクリプトジェネレーターAI YouTubeタイトル・概要欄ジェネレーターInstagramキャプションジェネレーターAI LinkedInヘッドライン・自己紹介ジェネレーターAI職務経歴書ブレットジェネレーターAIカバーレター作成ツールAIラップ歌詞ジェネレーターPDFフラット化ツールPDFロック解除（オーナーパスワード削除）PDFテキスト抽出PDFページ抽出PDF単語カウンターPDFにパスワードを設定PDFにページ番号を追加PDFページ並べ替えPDFページ削除PDF回転JPGをPDFに変換PDFをJPGに変換PDF圧縮PDF分割PDF結合PTからPXへの変換器PXからREMへの変換器トラからグラムへの変換器インドの土地単位変換器AI歌詞ジェネレーターAI詩ジェネレーターAIストーリージェネレーターAI翻訳AIテキスト要約ツールmgからmlへの変換器MPHからKMHへの変換器ノットからマイル毎時変換器立方メートルから立方フィート立方フィートから立方ヤード変換器平方フィートから平方メートル換算平方メートルから平方フィート変換器オンスからmlへの変換器mlからオンスへの変換器ガロンからリットル変換器リットルからガロン変換器キログラムからストーンへの変換器ストーンからキログラム変換器インチからミリメートルへの変換器ミリメートルからインチへの変換器マイルからキロメートル変換器キロメートルからマイル変換器華氏から摂氏への変換器摂氏から華氏への変換器バックパックサイズ電卓サーフボード容量電卓テニスグリップサイズ電卓ヘルメットサイズ電卓手袋サイズ電卓帽子サイズ変換スノーボードサイズ電卓スキーサイズ電卓スピードランスプリットタイマーステーブルフォード計算機ダーツチェックアウト電卓ボウリング・エコノミーレート電卓打撃ストライクレート電卓ネットランレート計算機KDレシオ計算機Eloレーティング計算機心拍数回復電卓ハイキング時間計算機ローイングペース計算機ランニング年齢グレード計算機FTP・パワーゾーン計算機Beepテスト電卓ACFTスコア電卓Wilks & DOTS 電卓ホイールオフセット電卓タイヤ負荷指数・速度レーティング検索マイルあたりコスト電卓リース買取電卓オクタン価ブレンド電卓2ストロークオイル混合電卓エンジン排気量計算ソファ搬入電卓薪コード計算機空気清浄機CADR電卓除湿機サイズ計算シーリングファンサイズ電卓カーテンサイズ計算機ラグサイズ電卓額縁の掛け高さ計算機テレビ取り付け高さ計算機テレビサイズ電卓池の容量・ライナー電卓プール塩量計算機プール容量計算給湯器サイズ電卓エポキシ樹脂計算機手すり子間隔電卓巾木とトリムの電卓サイディング計算機デッキ用ステインの計算芝生の種計算機芝生電卓アスファルト電卓立方ヤード電卓電線管充填率電卓直列並列コンデンサ電卓誘導リアクタンス計算機部屋の照明計算機ルクスからルーメン電卓ルーメンからワット変換器発電機サイズ計算機mAh Wh 変換器 電卓アンペアからワット電卓ワットからアンペア電卓摩擦計算機機械的倍率計算機音速計算機波の速度計算機浮力電卓終端速度計算機ド・ブロイ波長計算機光子エネルギー計算機emc2電卓時間の遅れ計算機ケプラーの第三法則計算機脱出速度計算機万有引力計算機ベール・ランベルトの法則電卓ネルンストの式計算機浸透圧計算機沸点上昇電卓凝固点降下計算パーセント組成計算機規定度計算機質量モル濃度計算機pKa→Ka変換器ヘンダーソン・ハッセルバルヒ電卓理論収量計算機制限反応物計算機電子配置計算機インタラクティブ周期表AI授業計画ジェネレーターAIクイズ作成ツール引用ジェネレーター (APA/MLA/Chicago)出席率計算APスコア計算機ACTスコア計算機SATスコア電卓youtube収益見積もりツールランダムRPGキャラクタージェネレーター