読者の皆さん、今回はDFS（Depth First Search）の概念について説明します。
これは、多くの競争的なコーディング試験でよく出題されるグラフの概念です。
それでは、Pythonを使ってDFSトラバーサルを作って見ましょう。
深さ優先探索とは？
深さ優先探索は、Stackデータ構造を利用して、グラフや木をたどるアルゴリズムです。
深さ優先探索のコンセプトは、「深さ」という言葉に由来している。
木はある枝の深さまでトラバースし、その後残りのノードまでバックトラバースします。
各反復のために訪問したノードを含む空の「スタック」を考える。
ここで行う作業は以下の通りです。
-
- ルートノードから開始し、スタックに格納します。
-
- 木に隣接するノードがないか調べ、1つのノードを選択します。
-
- 選択したノードの枝全体を走査し、すべてのノードをスタックにプッシュします。
-
- 枝の末端（これ以上隣接するノードがない）、つまりn番目の葉ノードに到達したら、一歩戻ってn-1番目のノードの隣接ノードを探す。
-
- n-1 番目のノードに隣接するノードがある場合、それらの枝を走査し、ノードをスタックにプッシュします。
深さ優先探索の概念 図解
以下のグラフの例を見てみましょう。
Stack : A |
Aはルートノードです。
Aはルートノードなので、これをスタックに格納します。
Stack : A B |
A-Bという枝に行きましょう。
Bは訪問されていないので、Bに行き、Bをスタックにプッシュします。
Stack: A B S C D |
ここで、A-B 分岐の終点に来たので、n-1 番目のノードである A に移動します。
今度は A の隣接ノードである S に注目します。
S を訪問し、スタックにプッシュします。
次に、S-C-D分岐を深さDまでたどり、S, C, Dを訪問済みとしてマークする必要があります。
Stack : A B S C D E H G |
D には他に隣接するノードがないので、C に戻り、その隣接する枝 E-H-G を深さまでたどり、それらをスタックにプッシュします。
Stack : A B S C D E H G F |
D に到達すると、隣接ノードすなわち未訪問のノードが 1 つだけ F にある。
F もスタックに押し込む。
graph1 = {
'A' : ['B','S'],
'B' : ['A'],
'C' : ['D','E','F','S'],
'D' : ['C'],
'E' : ['C','H'],
'F' : ['C','G'],
'G' : ['F','S'],
'H' : ['E','G'],
'S' : ['A','C','G']
} |
このスタック自体が DFS のトラバーサルです。
この記事もチェック：Pythonでグラフの深さ優先探索アルゴリズムを実装する方法を解説する
Pythonによる深さ優先探索アルゴリズムのコーディング
グラフを表現する方法には、隣接リストや隣接行列といったものがあることはご存じでしょう。
そこで、以下の例では、グラフの各ノードに対して隣接リストを定義しています。
def dfs(graph, node, visited):
if node not in visited:
visited.append(node)
for k in graph[node]:
dfs(graph,k, visited)
return visited
visited = dfs(graph1,'A', [])
print(visited)
|
注：この隣接表はユーザが入力することができ、ハードコードする必要はない。
グラフ（隣接リスト）、ノード、訪問済みノードのリストの3つのパラメータを入力とするDFS関数を定義します。
現在のノードが訪問されていない場合、つまり訪問済みリストに存在しない場合、それを訪問済みとしてマークし、訪問済みリストに追加します。
次のノードに移動し、そのノードを再帰的にDFS関数に渡す。
このようにして、各ノードは深さまで移動し、DFSの出力として表示されます。
graph1 = {
'A' : ['B','S'],
'B' : ['A'],
'C' : ['D','E','F','S'],
'D' : ['C'],
'E' : ['C','H'],
'F' : ['C','G'],
'G' : ['F','S'],
'H' : ['E','G'],
'S' : ['A','C','G']
}def dfs(graph, node, visited):
if node not in visited:
visited.append(node)
for k in graph[node]:
dfs(graph,k, visited)
return visited
visited = dfs(graph1,'A', [])
print(visited)
|
完全なコードと出力
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F'] |
上記のコードの出力は以下の通りです。
まとめ
DFSアルゴリズムに関するこのチュートリアルに沿って、コードと例を理解することができたと思います。
トラバーサルをよりよく理解するために、紙とペンを使って試してみてください。