作業フローを簡素化：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検索パーセンテージ減少電卓不可視文字除去ツール弧長電卓MACアドレス検索パーセント増加電卓ランダム誕生日ジェネレーター円錐展開図テンプレートジェネレーターランダムカラージェネレーター画像分割ツールwar電卓ランダム超能力ジェネレーター動画を結合エンジェルナンバー電卓シグマ記法電卓 総和パーセント誤差電卓合計電卓フィートとインチからセンチメートルへのコンバーター動画を逆再生英単語ランダム生成ツールYouTubeチャンネル統計標準偏差電卓 - 高精度ASCIIコード表MP3ルーパー平方完成電卓kva計算機売上総利益率電卓楕円円周電卓ai句読点追加番号を並べ替えるコラッツ予想電卓マン・ホイットニーのU検定計算機水星逆行カレンダービンゴカードジェネレーターFPSコンバーターHEX電卓ランダムトーナメント表作成ツール筆算割り算電卓相対標準偏差電卓熱膨張計算機私のIPアドレスは何ですかランダム絵文字ジェネレーターデシベル (dB) 電卓空の行を削除する手数料電卓逆テキスト血糖値コンバーター関数電卓中央値電卓対数電卓土星回帰電卓圧力電卓じゃんけんジェネレーターCAGR電卓HEXコンバーター動画を回転比率電卓水泳ペース計算機ビデオ速度を調整モジュロ電卓分数電卓ボウリングスコア計算機分散電卓 高精度t検定電卓労働時間計算ツールオンライン句読点削除ツール加速度電卓センチメートルからフィートとインチへのコンバーター正多角形電卓fena電卓ランダム名前ジェネレーター中間日計算機💧 露点電卓マスターナンバー電卓年の日電卓 - 今日は今年の何日目オーディオ スプリッター10進数からBCDへのコンバーターランダム時刻ジェネレーター画像回転ツール角速度計算機太陽位置計算機小数時間から普通の時間へのコンバーター文字数による改行相関係数計算機コラージュメーカーFacebookユーザーID検索log-base-2電卓表面積電卓ボクシングパンチ力計算機AIテキストヒューマナイザーatan2電卓ランダム日付ジェネレーターFIP電卓SRTからTXTへの変換ツールXMLバリデーターバイナリ電卓素数ですかBUN対クレアチニン比電卓クロスワードパズルメーカー外れ値電卓指数電卓-高精度動画から画像抽出ツール求人検索1マイルウォークテストロックポート電卓GIFメーカーアナグラム生成器配当利回り電卓CPM 電卓ジョルダン標準形電卓TikTok収益計算ツールボルト締付トルク計算機四次方程式計算機階段電卓csvからsrtへ魔方陣ジェネレーター🖱️ クリックカウンター二乗平均平方根電卓平均寿命電卓沸点計算ツールSRT 時間シフト 電卓バーコードジェネレーター変動係数電卓角度変換ツールANC電卓Twitch収益計算ツールサッカーxg期待ゴール電卓割り切れるテスト電卓パレットジェネレーター筆算足し算・引き算計算機迷路ジェネレーター配管流量電卓学習曲線電卓最小公倍数電卓桁数電卓積分電卓アンテナ長計算機ニュートン法電卓ピタゴラスの定理電卓ランダム映画ピッカージニ係数電卓タンジェント電卓ビデオをループ再生ランダムアニマルジェネレーターランダムトランプカードジェネレーター三角関数グラフ作成ツール赤ちゃんのミルク量計算斜辺電卓🔊 トーンジェネレーターノノグラムジェネレーター (ピクロス)ヒジュラ暦変換器ワイヤーゲージ電卓変化率電卓平方根電卓猫カロリー電卓科学表記法電卓馬力電卓⚔️ DPS電卓熱伝達計算機車両重量配分計算機PSIからbarへの変換器ランダムクレジットカードジェネレーター円錐台電卓BCDからバイナリへのコンバーターランダム算数問題ジェネレーター平均電卓-高精度平方数リストVTTからtxtへのコンバーターガウス分布ジェネレーターパスワード強度テスターヒストグラムメーカー並列抵抗電卓太陽・月・上昇星座電卓 🌞🌙✨IPアドレスから16進数への変換トルク電卓ランダムPIN生成器中間点電卓営業利益率電卓週番号計算機CRC32チェックサム電卓発音IPA変換ツールCMYKからHEXへの変換ツールサンプルサイズ電卓上下反転テキストジェネレーター動画圧縮四分位範囲電卓日割り家賃計算長方形の電卓10進数から16進数へのコンバーター3d距離電卓YouTubeショート収益化計算ツールZalgoテキストジェネレーターエラー関数電卓🎰 ガチャ天井計算機🎮 ゲーム感度変換器世界時計周波数波長変換ツール退職カウントダウンAIトークンカウンターHTMLからテキストコンバータパーセントからppmへのコンバーター打撃ストライクレート電卓ネットランレート計算機KDレシオ計算機Eloレーティング計算機心拍数回復電卓ハイキング時間計算機ローイングペース計算機ランニング年齢グレード計算機FTP・パワーゾーン計算機Beepテスト電卓ACFTスコア電卓Wilks & DOTS 電卓ホイールオフセット電卓タイヤ負荷指数・速度レーティング検索マイルあたりコスト電卓リース買取電卓オクタン価ブレンド電卓2ストロークオイル混合電卓エンジン排気量計算ソファ搬入電卓薪コード計算機空気清浄機CADR電卓除湿機サイズ計算シーリングファンサイズ電卓カーテンサイズ計算機ラグサイズ電卓額縁の掛け高さ計算機テレビ取り付け高さ計算機テレビサイズ電卓池の容量・ライナー電卓プール塩量計算機プール容量計算給湯器サイズ電卓エポキシ樹脂計算機手すり子間隔電卓巾木とトリムの電卓サイディング計算機デッキ用ステインの計算芝生の種計算機芝生電卓アスファルト電卓立方ヤード電卓電線管充填率電卓直列並列コンデンサ電卓誘導リアクタンス計算機部屋の照明計算機ルクスからルーメン電卓ルーメンからワット変換器発電機サイズ計算機mAh Wh 変換器 電卓三相電力計算機アンペアからワット電卓ワットからアンペア電卓直列抵抗計算機摩擦計算機斜面計算機機械的倍率計算機音速計算機波の速度計算機浮力電卓終端速度計算機ド・ブロイ波長計算機光子エネルギー計算機emc2電卓時間の遅れ計算機ケプラーの第三法則計算機脱出速度計算機万有引力計算機ベール・ランベルトの法則電卓ネルンストの式計算機浸透圧計算機沸点上昇電卓凝固点降下計算パーセント組成計算機規定度計算機質量モル濃度計算機pKa→Ka変換器ヘンダーソン・ハッセルバルヒ電卓理論収量計算機制限反応物計算機電子配置計算機インタラクティブ周期表AI授業計画ジェネレーターAIクイズ作成ツール引用ジェネレーター (APA/MLA/Chicago)出席率計算APスコア計算機ACTスコア計算機SATスコア電卓パーセンテージからCGPA変換器CGPAからパーセンテージへの変換器簡単採点ツール EZ Grader子育て費用計算機おむつサイズ電卓赤ちゃんの名前ジェネレーター赤ちゃんの目の色予測子供のBMIパーセンタイル計算機子供の身長予測ツールhcg倍加時間計算ツール体外受精出産予定日電卓着床計算ツール中国式性別予測カレンダーISO 8601 日付フォーマッターユリウス日変換器昼寝電卓月相電卓日の出＆日の入り電卓日付ローマ数字変換電卓ソブリエティ計算機ハーフバースデー計算機記念日計算機チップ分配計算機メールマーケティングROI電卓リード獲得単価計算機運転資本計算機youtube収益見積もりツールランダムRPGキャラクタージェネレーター