todo: 一筆書きについて書く
| 無向グラフ | 有向グラフ | |
|---|---|---|
| 二部グラフ判定 | 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以上
| 行きがけ済 | 帰りがけ済 | 状況 |
|---|---|---|
| False | False | これから訪問するかも |
| False | True | (ありえない) |
| True | False | |
| True | True | その点から帰りがけ未完の点には行けない |
todo: トポソートとかも説明できるようないい感じの解釈がほしい
（なかなか難しい。DFS木と一緒に考えるとわかりやすい？）