深さ優先探索とは
深さ優先探索（Depth First Search、通称DFS）とは、目的のノードを見つけるか全てを探索し終わるまで探索を続けるアルゴリズムです。幅優先探索と違い、分岐があってもとりあえず深い方へ進むことが特徴です。
木構造のノードを探索する順に番号をつけてみるとこうなります。
では、実際にコードを書いてみます。
使用例
1.単純な木構造の探索
先ほどと同じ木構造の番号を少し変えて、ノードの番号を探索する順（行きがけ順）に出力するプログラムを書いてみます。
コード
def dfs(pos):
print(pos, end=' ')
for i in tree[pos]:
dfs(i)
tree = [[1, 2, 3], [4, 5], [], [6, 7], [8, 9], [], [10], [], [], [], []]
dfs(0)
# 0 1 4 8 9 5 2 3 6 10 7
解説
-
treeに木構造の値をセットする - 0のノードからスタートするので、
dfs(0)で始める -
pos（現在のノード）を出力 -
posの直下のノードを探索
1~4の操作について詳しく説明していきます。
まず、treeというリストに木構造を表すように値をセットしておきます。例えば1番目のノードからは4と5のノードに行けるので、tree[1]=[4, 5]とセットします。
データの準備ができたら、今回は0番目のノードから探索を開始するのでdfs(0)として操作を開始します。
それでは関数dfsの中身に移ります。
今回の目標は**「深さ優先探索で探索する順にノードの番号を出力する」**ことなので、まず現在探索を行なっているノード（pos）を出力します。
その後、自分の直下の要素には何があるか探索します。
例えば現在のノードが1の場合、直下のノードは4と5です。
まず4に関して、同じようにdfs(4)を行います。4の直下には8と9があるので、今の時点での順番としては1→4→8となっています。ただ、8の下には要素がないので、そこは**「行き止まり」**ということになります。
**「行き止まり」**になったら一つ前の分岐まで戻ります。この場合は9ですね。
9の下にも要素はないので、また一つ前の分岐に戻り、5を探索することになります。
上記の作業を全ての要素に関して繰り返すと、探索された順に番号を出力することができます。
2.Tour（ABC204_C）
ある国に、1~Nの番号がついたN個の都市と、1~Mの番号がついたM個の道路があります。道路iを通ると、都市$A_i$から都市$B_i$へ移動することができます。都市$B_i$から都市$A_i$への移動はできません。どこかの都市からスタートし、0本以上の道路を使い移動して、どこかの都市をゴールとする時、スタート地点とゴール地点の都市の組として考えられるものは何通りあるかを出力するプログラムを書いてみます。
入力形式
N M
A1 B1
A2 B2
.
.
AM BM
入力例
3 3
1 2
2 3
3 2
コード
import sys
# 再起回数の上限を上げておく
sys.setrecursionlimit(10000)
# 入力の読み込み
N, M = map(int,input().split())
road = [[] for i in range(N + 1)]
# 直接道路でつながっている都市のリストを作成
for i in range(M):
A, B=map(int,input().split())
road[A].append(B)
def dfs(s):
if goal[s]: return # もう既に出てきた都市であればreturn
goal[s] = True
for r in road[s]: dfs(r)
ans = 0
# 都市iからスタート
for i in range(1, N + 1):
goal = [False] * (N + 1) # goal[x]は、都市iから都市xへ行くことができるかどうかを表す
dfs(i)
ans += sum(goal)
print(ans)
解説
- 入力を読み込む
- 都市iからスタートし、他のどの都市に行くことができるかを関数
dfsを用いて判断する - 都市iから行くことのできる都市の数を
ansに足す - 2、3をiが1~Nの間繰り返す
-
ansを出力
では、説明していきます。
問題1を思い出してください。木構造をリストで表す際、
1番目のノードからは4と5のノードに行けるので、
tree[1]=[4, 5]とセットします。
と書いていました。
今回、$A_i$ $B_i$という形で**「都市Aiから都市Biに行くことができますよ」**、という情報が与えられます。その情報をroadという名前のリストに入れてわかりやすくしてあげましょう。1の問題と同じように考えると、例えば$A_i$ $B_i$が2 3だった場合、road[2] = [3]と表すことができます。
roadリストの用意ができたら、肝心の探索に移っていきます。と言っても、やることは問題1とそれほど変わりません。スタートする都市を決めたら、その下のノードを辿っていくだけです。
例を見てみましょう。
都市1からスタートすることにします。
探索を始める前に、goalというリストを用意しておきました。このリストは、都市iからどの都市に移動することができるかを表します。goal[x] = Trueとなっていれば、都市iから都市xに移動することができるという意味になります。
それではdfs(1)を行います。
まず、都市1から都市1に行くことは可能なのでgoal[1] = Trueとなります。
次に、road[1] = [2]より都市1から都市2に移動できることがわかるので、dfs(2)に移ります。
goal[2] = Trueとなり、road[2] = [3]よりdfs(3)に移ります。
goal[3] = Trueとなり、road[3] = [2]よりdfs(2)に移ります。
ここで注意です！goal[2]は既にTrueとなっています。これが何を意味するかというと、「都市2には既に来たことがある」、つまり**「行き止まり」**です。「行き止まり」になってしまったので、この探索は終了となります（return）。
つまり、goal = [False, True, True, True]となるので都市1からは3つの都市に移動できることがわかりました。
これらの操作をスタートする都市（i）が1~Nまで繰り返せば、スタート地点とゴール地点の都市の組の数をansとして得ることができます。
他のアルゴリズムに関する記事
筆者より
アルゴリズム初心者なので、間違っている点や説明不足な点は教えていただけるとありがたいです！