Appearance
グラフ
最短経路
| アルゴリズム | 何ができるか | 適用条件 | 計算量 |
|---|---|---|---|
| BFS | 単一始点最短経路 | 重みなし | O(V+E) |
| 0-1 BFS | 単一始点最短経路 | 辺重みが0か1 | O(V+E) |
| Dijkstra | 単一始点最短経路 | 辺重みが非負 | O((V+E) log V) |
| Bellman-Ford | 単一始点最短経路・負閉路検出 | 負辺も可 | O(VE) |
| Warshall-Floyd | 全点対最短経路 | 負辺も可・負閉路検出可能 | O(V³) |
探索・連結性・構造
| アルゴリズム | 何ができるか | 計算量 |
|---|---|---|
| DFS | 深さ優先探索・到達可能性・連結成分 | O(V+E) |
| BFS | 幅優先探索・到達可能性・連結成分 | O(V+E) |
| Union Find | 無向グラフの連結性の管理 | 償却 O(α(V)) / 操作 |
| SCC | 強連結成分分解・DAGへの縮約 | O(V+E) |
| トポロジカルソート | DAGの順序付け・閉路検出 | O(V+E) |
| 二部グラフ判定 | 二部グラフ判定・2グループ分け | O(V+E) |
| サイクル検出 | 有向・無向グラフの閉路検出と復元 | O(V+E) |
木
| アルゴリズム | 何ができるか | 計算量 |
|---|---|---|
| 木の直径 | 木の最長パス・両端点の取得 | O(V) |
| LCA | 木の2頂点の最小共通祖先・距離 | 前処理 O(V log V)、クエリ O(log V) |
| オイラーツアー | 部分木の区間化・部分木クエリ | O(V) |
全域木
| アルゴリズム | 何ができるか | 計算量 |
|---|---|---|
| Kruskal | 最小全域木 | O(E log E + E α(V)) |
| Prim | 最小全域木 | O((V+E) log V) |
フロー
| アルゴリズム | 何ができるか |
|---|---|
| 最大フロー | 最大流量・最小カット・二部マッチング |
| 最小費用流 | 指定した流量を最小コストで流す |
グラフ構造
| 名前 | 特徴・何ができるか |
|---|---|
| Functional Graph | 各頂点の出次数が1、サイクルと木からなる |
| DAG | 有向閉路がなく、トポロジカル順にDPができる |
注意点
- Dijkstraは負辺があると正しく動作しない場合がある
- BFSは重みなしグラフの最短経路に使える
- DFSは一般グラフの最短距離を求めるものではない
- DFSは再帰が深くなる場合にスタックオーバーフローに注意