| 無向グラフ | 有向グラフ | |
|---|---|---|
| 二部グラフ判定 | UF, BFS, DFS | x |
| s-tパス判定 | UF, BFS, DFS | BFS, DFS |
| 連結か判定 | UF, BFS, DFS | BFS, DFS |
| 連結成分数 | UF, BFS, DFS | BFS, DFS |
| サイクル検出 | UF, BFS, DFS | BFS, DFS |
| トポロジカルソート | x | BFS, DFS |
| 頂点からの距離 | BFS | BFS |
| UF | DFS | BFS | |
|---|---|---|---|
| 二部グラフ判定 | 倍化する | ||
| 二部グラフでないとは、長さが奇数の閉路を持つことであることを利用する。 | 距離の偶奇が矛盾しないか判定 | 距離の偶奇が矛盾しないか判定 | |
| s-tパス判定 | |||
| 連結か判定 | |||
| 連結成分数 | |||
| サイクル検出 | union 操作で変化がない→サイクルがある | 行きがけで訪問しているが帰りがけで訪問していない点にたどり着いたら、サイクルあり | 入次数0の点を除くのを繰り返して、点が残る場合サイクルあり |
| (サイクルの頂点はすべて入次数が1以上) | |||
| トポロジカルソート | x | 帰りがけ順の逆順を連結成分ごとに調べる | 入次数0の点を除くのを繰り返す |
| 頂点からの距離 | x | x |
サイクル上のすべての点は入次数が1以上だし、出次数が1以上
有向グラフの場合、連結判定は UF ではできないので注意。
（次数を考えるのは何が嬉しい？）
問題例