DAG，トポロジカルソート
1. 用語の概要
DAG
Directed Acyclic Graph．サイクル（有向閉路ともいう）を含まない（Acyclic）有向（Directed）グラフ
有向グラフがサイクルを含むか否か，判定する必要あり
トポロジカルソート
有向グラフの各点に番号を付ける．
どの有向枝も，始点の番号＜終点の番号になるように付ける
トポロジカルソートができる ⇔ DAG
トポロジカルソート（番号付け）は一般に一意ではない
入次数
有向グラフにおいて，ある点に入る枝の数．ある点から出る枝の数は，出次数
2. トポロジカルソートの実装（Kahnのアルゴリズム）
(1) 概要
$ O(|V|+|E|)
基本的にqueue（キュー）を使う．幅優先探索（BFS）に似ている．
入次数0の点から順に番号を付け，番号を付けた点とその点から出ている枝を削除する
上の処理を繰り返す
全ての点に番号が付けば，トポロジカルソート完了．番号ついていない点があれば，ソート不可 ⇔ サイクルあり．
(2) コード例
code:python
# Kahnのアルゴリズムでトポロジカルソート．1-index
from collections import deque
N = 4
q = deque([v for v in range(1, N + 1) if in_degv == 0]) # 入次数0の点をキューに入れる order = [] # トポロジカルソート用
while q:
v = q.popleft() # 入次数0の点vを獲得
order.append(v)
in_degu -= 1 # 点vから出る枝を削除して，終点の入次数を-1 q.append(u) # 入次数0になれば，キューに追加
# print(v, in_deg, order)
if sum(in_deg) == 0: # 全て枝がなくなれば，トポロジカルソート可能．サイクルなし
print(*order)
else:
print('サイクルが存在します．')
# 出力結果: 1 3 2 4
練習問題
3. トポロジカルソートの実装（DFS）
(1) 概要
$ O(|V|+|E|)
DFSで探索途中で，探索経路上にある点に戻ってきたら「サイクルあり！」と判定
行きがけ順の意味で訪問済みなのか，帰りがけ順の意味で訪問済みなのか，の区別が重要．
「サイクルあり！」なのは，行きがけ順の意味で訪問済みの点を見つけたとき．
帰りがけの順に点を保存し，逆順に表示すればトポロジカルソート
(2) コード例
code: python
# DFSでトポロジカルソート
import sys
sys.setrecursionlimit(1000000)
def main():
def dfs(v):
continue # 帰りがけで訪問済みの点は探索しない．サイクルでもない
return False # サイクル発見
if not dfs(u):
return False # 点u以降でサイクル発見
order.append(v)
return True
N = 4
f_visited = False * (N + 1) # 行きがけで訪問済み b_visited = False * (N + 1) # 帰りがけで訪問済み order = [] # トポロジカルソート順に，点indexを格納
for v in range(1, N + 1):
if not dfs(v):
print('サイクルが存在します．')
exit()
print(*reversed(order)) # トポロジカルソート可能．サイクルなし
main()
# 出力結果: 1 3 2 4
再帰関数を使うので，sys.setrecursionlimitの設定が必要．
AtCoderで再帰関数を使うときは，PyPy3よりPython推奨．
4. トポロジカルソート（Kahnのアルゴリズム）の応用
DFSによる方法は実装が難しそう．
(1) 最長経路長
DAGにおける最長経路長を求める
一種のDP．dist[v]：点vを終点とする最長経路長
次数0の点をキューに追加するときに，dist[v]を更新
(2) 辞書順で最も小さいトポロジカルソート
トポロジカルソートとなっている並び方のうち，辞書順で最小の並び方を発見
キューに2つ以上の点がある場合，indexの小さい方から選択する．優先度付きキュー（ヒープ）を使う．