クエリの実行方法
- 01グラフを読み込みます。DAG プリセットは 7 ノードの有向非巡回グラフです。Bridge プリセットは無向の三角形と鎖を持ち、Cycle C₅ プリセットに Directed トグルを加えると単一の有向リングになります。
- 02Order & connectivity タブでアルゴリズムを選びます。Topological sort は無向グラフをきっぱり拒否し、その理由を説明します。
- 03行を読みます。Topological sort は順序、層の数、層ごとに 1 行を出力します。連結性アルゴリズムは成分リスト、関節点、橋、または辺成分の数を出力します。
- 04走査を眺めます。Topological sort は入次数と除去をたどり、Cycle detection は閉じる辺をキャンバス上でハイライトします。
計算例
| グラフ · アルゴリズム |
計算結果 |
| DAG プリセット · Topological sort |
順序 A → B → C → D → E → F → G、層 5 — L1 A、L2 B, C、L3 D、L4 E, F、L5 G |
| Bridge プリセット · Cut vertices & bridges |
関節点 B, D, E、橋 D–E, B–D、辺成分 3 — A, B, C · D · E, F, G |
| Cycle C₅ + Directed · Strongly connected |
成分数 1、E, D, C, B, A を含む |
| DAG プリセット · Strongly connected |
成分数 7、各ノードが 1 つの単独成分 |
| 既定グラフ · Cycle detection |
閉路あり Yes、閉路 A → B → C → A、理由 Back edge C – A |
| DAG プリセット · Cycle detection |
閉路あり No、理由 No back edge ⇒ directed acyclic graph |
DAG の層は実行計画です。A が最初、次に B と C が任意の順で、次に D、次に E と F、最後に G です。Bridge プリセットは、1 本の橋がグラフを 3 つに分ける理由を示します。B–D と D–E が、三角形 A–B–C、単独ノード D、三角形 E–F–G をつなぐ唯一の接続です。
トグルが答えを変える理由
既定グラフには三角形 A–B–C が含まれ、Cycle detection は A → B → C → A と理由 Back edge C – A を報告します。Directed をオンにすると同じ 3 本の辺は前向きにしか向かなくなり(A→B、B→C、A→C)、検出器は No、理由 No back edge ⇒ directed acyclic graph と答え、以前は "Topological sort is defined for directed graphs only — switch the graph to directed first" を返していた Topological sort が順序 A → B → C → D → E → F、6 層で成功します。1 つのトグルで正反対の 2 つの判定。辺の向きがすべてです。
限界
- Topological sort は有向専用です。
- 向きを推測せず、無向入力を拒否します。強連結性も有向グラフに対して定義されます。無向グラフでは、同じパネルの Components が到達可能性の問いに答えます。
- できないこと。
- 重み付きタスクのスケジューリング、グラフ彩色、複数のトポロジカル順序の生成は行いません。キャンバスは 1 つの有効な順序を示し、他の順序を探るには辺を編集します。
活用場面
ビルドと依存の順序
DAG プリセットは小さなビルド計画のように読めます。層の行は並列に実行できるもの(B, C、次に E, F)と、その後ろで直列化されるもの(D、次に G)を教えてくれます。新しい依存がループを閉じると、Cycle detection は壊れた順序を返す代わりに後退辺を名指しします。
脆弱性のレビュー
Bridge プリセットでは、B–D または D–E を失うと 3 つのグループが分断され、単独ノード D は到達不能になります。孤立ノードのあるグラフで Components を実行すると、もう 1 つの故障モードが見えます。既定グラフを構築してノードを 1 つ追加すると、成分数は 2、最大成分は 6 と読め、Traversal パネルは同じノードを A から到達不能として一覧します。
プライバシー
順序付けと連結性の作業はすべてブラウザ内で実行され、グラフがページから出ることはありません。
参考文献
- Wikipedia, Topological sorting, en.wikipedia.org (访问日期:2026-10-07)— DAG の順序と層分け。
- Wikipedia, Strongly connected component, en.wikipedia.org (访问日期:2026-10-07)— 有向グラフの相互到達可能性。
- Wikipedia, Biconnected component, en.wikipedia.org (访问日期:2026-10-07)— 関節点、橋、辺成分。
- Wikipedia, Cycle detection, en.wikipedia.org (访问日期:2026-10-07)— 閉路の証拠としての後退辺。
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
- Updated