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()
while Stack:
x, frm = Stack.pop()
if x < 0:
PostOrder.append(~x)
continue
if Parentx >= 0: continue PreOrder.append(x)
if Parenty >= 0: continue return Parent, PreOrder, PostOrder, Depth