ナビゲーションアルゴリズムDFS/BFS

*Python付きの整理ノートです.

📍必要な資料構造の基礎

スタック先入後出構造または後入先出構造

stack = []

# 삽입(5-2-3-7) - 삭제 - 삽입(4) - 삭제
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() #7 삭제
stack.append(1)
stack.append(4)
stack.pop() #4 삭제

print(stack) #[5,2,3,1]

append()およびpop()メソッドを使用すると、スタックデータ構造と同じ動作を実行できます.
append()は一番後ろにデータを挿入し,pop()メソッドはリストの一番後ろからデータを取り出す.
キュー先入先出構造

from collections import deque

queue = deque()

# 삽입(5-2-3-7) - 삭제 - 삽입(1-4) - 삭제
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() #5 삭제
queue.append(1)
queue.append(4)
queue.popleft() #2 삭제

print(queue) #deque([3,7,1,4])

📌 Pythonキューを実装する場合、collectionsモジュールを使用して提供されるライブラリは有効です!

DFS

DFSは深さ優先ナビゲーションとも呼ばれ,グラフィックにおける深さ優先のアルゴリズムである.
DFSはスタックデータ構造(または再帰関数)を使用する.

📍DFSアルゴリズム

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

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

ステップ

は、2番目の処理が実行されなくなるまで繰り返される.

DFSナビゲーション順序1>2>7>6>8>3>4>5

def dfs(graph,v,visited):
    #현재 노드를 방문 처리
    visited[v] = True
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph,i,visited)
            
#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * 9

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

📌 DFSスタックを用いたアルゴリズムであるため,再帰関数を用いた場合の実装は非常に簡潔である.

BFS

BFSは幅優先ナビゲーションとも呼ばれ,隣接ノードからのナビゲーションを開始するアルゴリズムである.
BFSはキューデータ構造を使用する.

📍BFSアルゴリズム

ナビゲーション開始ノードをキューに挿入し、アクセス処理を行う.

キューからノードを取り出し、そのノードのすべての隣接ノードのうちアクセスしていないノードをキューに挿入し、

にアクセスする.
ステップ

は、2番目の処理が実行されなくなるまで繰り返される.

BFSナビゲーション順序1>2>3>8>7>4>5>6

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start]) #시작 노드를 큐에 넣고 시작
    #현재 노드를 방문처리
    visited[start] = True
    #큐가 빌 때까지 반복
    while queue:
    	#큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        #아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * 9

#정의된 DFS함수 호출
bfs(graph,1,visited)

DFSSBFS動作原理スタックキューの実現方法再帰関数を用いたキューデータ構造