深さ優先探索

深さ優先探索
ノードからノードへ下へ降りていき、突き当たったら分岐点まで戻り、
また未開のノードへと降りていくアルゴリズム。
再帰を使ってコードを書きました。

具体例として上記の木に対して深さ優先探索をしました。

# python3
# sys.setrecursionlimit(10000) #再帰の回数上限変更 (デフォルト1000回)

# 各ノードから,どのノードにエッジ(枝)が伸びているか調べてリスト化する (隣接リスト)
edge = [[1, 2], [0, 3, 4], [0, 5], [1], [1], [2]]

def dfs(now, before=-1):#before:一つ前に通ったノード
    if before==-1:
        print(now)
    for c in edge[now]: #c:子
        if not c ==before: #無限ループを防ぐ
            print(c)
            dfs(c, now) #再帰

dfs(0)

出力結果

0
1
3
4
2
5

ありがとうございました。