DFS
非再帰で行きがけ帰りがけ順とdfs木を構成
code: dfs_postorder.py
def dfs(G, s):
"""
G := 隣接頂点リスト
s := 開始頂点
O(|V| + |E|)
"""
N = len(G)
Depth = 0 * N # 各頂点のdfs木における深さ
Parent = -1 * N # dfs木の親リスト（根の親は便宜上N）
PreOrder = [] # dfsの行きがけ順
PostOrder = [] # dfsの帰りがけ順
Stack = deque()
Stack.append(s, N)
while Stack:
x, frm = Stack.pop()
if x < 0:
PostOrder.append(~x)
continue
if Parentx >= 0: continue
Parentx = frm
PreOrder.append(x)
Stack.append(~x, 0)
for y in Gx:
if Parenty >= 0: continue
Stack.append(y, x)
Depthy = Depthx + 1
return Parent, PreOrder, PostOrder, Depth