グラフ理論ワークベンチ：最短経路・MST・中心性

グラフ理論ワークベンチはブラウザのキャンバス上にグラフを構築し、21 個の古典的アルゴリズムを実行します。作業は 6 つのパネルに分かれます: Traversal（BFS、DFS）、Shortest path（Dijkstra、A*、Bellman–Ford、Floyd–Warshall）、Spanning tree（Prim、Kruskal）、Order & connectivity（トポロジカルソート、連結成分、関節点と橋、閉路検出）、Flow & matching（Dinic、Edmonds–Karp、二部判定、ハンガリー法マッチング）、Metrics & centrality（次数 / 直径 / 内周、Brandes 中心性、PageRank、オイラー路）。プリセットは完全グラフ、閉路グラフ、二部グラフ、グリッドグラフ、ペテルセングラフ、DAG、フローネットワーク、負の重み、橋をカバーします。各パネルには独自の URL があり、いくつかの実行はステップごとに再生されます。

更新 2026-10-015 个来源约 4 分钟读完

アルゴリズムの実行方法

パネルを選ぶ— タブバーから Traversal、Shortest path、Spanning tree、Order & connectivity、Flow & matching、Metrics & centrality を選択。
グラフを構築する。プリセットを選んで Build を押すか、Move / connect で 2 つのノードを順にクリックして辺を切り替えます。Add node と Delete で頂点を編集します。重みは辺リストまたは隣接行列に入力します（0 = 辺なし）。
アルゴリズムと入力を設定する— BFS、DFS、Prim には Source、Dijkstra、A*、Floyd–Warshall には Source と Target、フローには Source と Sink、ほかに A* のヒューリスティックと PageRank の減衰率。
結果テーブルを読む。ヘッダーに手法と信頼レベルが表示され、行には距離、経路、木の重み、フロー、ランキングが並び、キャンバスはアルゴリズムが見つけたものを色分けします。
ステップ実行と再利用。アニメーション実行では Play、Prev、Next とスライダーが使えます。カードを公開するか、隣接行列と辺テーブルをワークスペースに書き出します。

計算例

既定のグラフは 6 ノードの無向の例です: A–B 4、A–C 2、B–C 1、B–D 5、C–D 8、C–E 10、D–E 2、D–F 6、E–F 3。以下の各計算結果はパネルによるものです。

パネル · アルゴリズム	入力	計算結果
Shortest path · Dijkstra	Source A、Target F	距離 13、経路 A → C → B → D → E → F、確定順 A → C → B → D → E → F
Traversal · BFS	Source A	訪問順 A → B → C → D → E → F、最大層 3、木の辺 5 本
Spanning tree · Kruskal	既定のグラフ	総重み 13、選択した辺 5 / 9、連結成分 1
Flow & matching · Dinic	Flow network S→T プリセット	最大流 19、最小カット容量 19、カット辺 S→A、B→D
Metrics · Degree / diameter / girth	Petersen プリセット	10 ノード / 15 辺、直径 2、半径 2、内周 5、三角形 0

これらの整数の重みにより経路と木の和は正確に保たれ、フローの値は最小カットと照合されます。BFS はホップ数、Dijkstra は重みを測ります。A からはどちらも F に到達しますが、BFS は 3、Dijkstra は 13 と答えます。フローパネルは Dinic を Edmonds–Karp と照合し、同じ 19 になります。

答えが止まる範囲

Traversal、中心性、PageRank は重みではなくホップ数を数えます。: 中心性パネルは、中心性が重みなし（ホップ数ベース）の経路を使い、辺の重みを無視すると警告します。重み付きの答えは Shortest path、Spanning tree、Flow の各パネルから得られます。
大きなグラフでは行列エディタが隠れます。: 14 ノードを超えるとセルエディタが貼り付けボックスに置き換わり、行列をまとめて読み込みます。
スペクトル的・記号的なグラフ処理は行いません。: ラプラシアン固有値の計算、同型判定、グラフファイルのインポートは行いません。隣接行列をワークスペースに書き出し、行列代数は math tools、統計モデルは stats、単一式は scientific calculator に持っていってください。

方向の落とし穴

Directed トグルは各パネルに一様に効くレンズではありません。既定のグラフで Shortest path を Source F、Target A にすると、無向モードは F → E → D → B → C → A に沿って 13 と答えます。Directed に切り替えると同じ問い合わせは ∞、経路 unreachable と答えます。F の両方の辺がそこへ向かって入ってくるためです（D → F と E → F）。Directed を有効にしたまま Spanning tree に切り替えても Prim の答えは変わらず、総重み 13 で、警告 "Input is directed; this algorithm treats it as undirected (edge direction ignored)" が付きます。Components、cut vertices and bridges、二部判定も同じ読み方をし、Topological sort は無向モードをきっぱり拒否します。

どこで役立つか

最短経路と走査を教える

既定のグラフで BFS と Dijkstra を実行します。BFS は F を 3 ホップ、Dijkstra は 13 重み単位で報告し、スライダーが各確定・緩和ステップをたどります。Dijkstra は負の重みを拒否し、同じパネルの Bellman–Ford を指します。

容量計画

Flow network S→T プリセットは最大流 19、最小カット容量 19、カット辺 S→A と B→D を返し、照合行は Edmonds–Karp も 19 に達することを確認します。K₃,₃ では Hungarian パネルが最大マッチング 3 と同サイズの最小頂点被覆を返します。