[アルゴリズム]DFS(深度優先ナビゲーション)

2021-07-22
! 約3週間のアプリの面白さの中、ずっとアプリを作っていましたが、今は日常生活に戻り、アルゴリズムの勉強を再開します.前回実施を学習したので、今回は次章DFS/BFSの学習内容を書きました.
<資料:Pythonを用いたエンコードテストです>

1.スタック、キュー

DFSとBFSは代表的なナビゲーションアルゴリズムであり、両者をよりよく理解するためには、まず基本的なデータ構造スタックとキューを理解しなければならないが、私は学校のデータ構造の授業で学んだので、簡単に詳細を書き、省略する.
スタックは、先入後出(FIFO)または後入先出(LIFO)構造であり、キューは先入先出(FIFO)構造である.
Pythonキューを実装する場合、collectionsモジュールで提供されるdequeデータ構造を使用すると便利です.

2.DFS（深度優先ナビゲーション）

グラフィックで深部を優先的にブラウズするアルゴリズム.

DFSはスタックデータ構造を採用し、具体的な操作過程は以下の通りである.

ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行います.

スタックの最上位ノードにアクセスされていない隣接ノードがある場合は、スタックに格納してアクセス処理を行います.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.

これ以上実行できないまで、2番目のプロセスを繰り返します.

図に示すように、

開始ノード「1」をスタックに挿入し、アクセス処理を行います.

スタックの最上位ノード(「1」)にアクセスしていない隣接ノードの小ノード「2」をスタックに入れてアクセス処理を行います.

スタックの最上位ノード(「2」)にアクセスしていない隣接ノードで、スタックに小さなノード「3」を入れてアクセス処理を行います.

最上位ノード(「3」)にはアクセスされていない隣接ノードがないため、スタックから「3」を取り出します.

同様に、「2」もスタックから取り出します.

次のスタックにアクセスしていない最上位ノード(「1」)の隣接ノード「4」をスタックに入れてアクセス処理を行います.

未アクセスのノードがないまでアクセスを続行

手順:1-2-3-4-5-6
DFSはスタックを用いたアルゴリズムであり,実際の実装では再帰関数を用いた場合に簡潔さを実現できる.

3.サンプルコード

def dfs(graph, v, visited):
	visited[v] = True  #방문처리
    print(v, end=' ')
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
graph = [
	[],
    [2,4],
    [1,3],
    [2],
    [1,5,6],
    [4,6],
    [4,5]
    ]    		#2차원 리스트로 표현
    
visited = [False] * 9

dfs(graph, 1, visited)	#DFS 함수 호출

DFS/BFS問題を解いたときに感じたことは,両者を正確に区別することは難しい.
したがって、すべてのノードにアクセスする必要がある場合、迷路に移動するたびに重みが増し、移動中に制約がある場合はDFSが使用されます.