【競プロ】dfsの行きがけ順と帰りがけ順の違い

毎回解説とかで、わからなくなるので、備忘録として記載。

帰りがけ順 (Post-order Traversal)

帰りがけ順では、あるノードvに対してその子ノードの探索（dfs）をすべて終えた後に、そのノードvを処理します。これをコードで表現すると、以下のようになります（depはノードを処理するための関数や値を保持する配列などを想定しています）

def dfs(v, parent):
    ope = 0
    for child in children_of(v):
        if child != parent:  # 親ノード以外を探索
            ope = dfs(child, v)
    # 子ノードの探索が全て終わった後にノードvを処理
    dep[v] = ope

先に1番深い子から処理していく。最後に親ノードが処理される

行きがけ順 (Pre-order Traversal)

行きがけ順では、あるノードvをその子ノードを探索する前に処理します。これは、ノードvに最初に到達した時点で何らかの操作を行うことを意味します。コードでの表現は以下の通りです

def dfs(v, parent):
    dep[v] = dep[parent] + 1  # ノードvを処理
    for child in children_of(v):
        if child != parent:  # 親ノード以外を探索
            dfs(child, v)

先に親ノードから処理していく。最後に末端の子ノードが処理される