Pythonのグラフの深さ優先探索アルゴリズムを初心者にわかりやすく解説する

スポンサーリンク

読者の皆さん、今回はDFS(Depth First Search)の概念について説明します。

これは、多くの競争的なコーディング試験でよく出題されるグラフの概念です。

それでは、Pythonを使ってDFSトラバーサルを作って見ましょう。

スポンサーリンク

深さ優先探索とは?

深さ優先探索は、Stackデータ構造を利用して、グラフや木をたどるアルゴリズムです。

深さ優先探索のコンセプトは、「深さ」という言葉に由来している。

木はある枝の深さまでトラバースし、その後残りのノードまでバックトラバースします。

各反復のために訪問したノードを含む空の「スタック」を考える。

ここで行う作業は以下の通りです。

    1. ルートノードから開始し、スタックに格納します。
    1. 木に隣接するノードがないか調べ、1つのノードを選択します。
    1. 選択したノードの枝全体を走査し、すべてのノードをスタックにプッシュします。
    1. 枝の末端(これ以上隣接するノードがない)、つまりn番目の葉ノードに到達したら、一歩戻ってn-1番目のノードの隣接ノードを探す。
    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による深さ優先探索アルゴリズムのコーディング

グラフを表現する方法には、隣接リストや隣接行列といったものがあることはご存じでしょう。

そこで、以下の例では、グラフの各ノードに対して隣接リストを定義しています。

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']

上記のコードの出力は以下の通りです。

Image 8
Example Graph

まとめ

DFSアルゴリズムに関するこのチュートリアルに沿って、コードと例を理解することができたと思います。

トラバーサルをよりよく理解するために、紙とペンを使って試してみてください。

タイトルとURLをコピーしました