LoginSignup
2
1

More than 3 years have passed since last update.

深さ優先探索

Last updated at Posted at 2020-01-03

深さ優先探索
ノードからノードへ下へ降りていき、突き当たったら分岐点まで戻り、
また未開のノードへと降りていくアルゴリズム。
再帰を使ってコードを書きました。
キャプチャ.PNG
具体例として上記の木に対して深さ優先探索をしました。

#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

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

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1