DFS / BFS

エクスプローラ(Search):大量のデータから必要なデータを検索するプロセス
中でもDFS/BFSの使用が最も多い
1.スタック(Stack):DFSで使用

先入力後出力データ構造

入口と出口は同じ形でプリンスを連想すればいい

Pythonでリスト構造挿入/削除(pop)機能を用いて

を実現する.
2.キュー:BFSで使用

先進データ先進先出資料構造

入口も出口も貫通するトンネル形態を連想すると

となる.

リストデータ型を使用すると時間的複雑度が高いため、Dequeライブラリ

を使用する.

from collections import deque 

# 큐(Queue) 구현을 위해 덱(Deque) 라이브러리 이용
queue = deque()

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

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

3.再帰関数:DFSでよく使われる概念で、自分を再呼び出しする関数です.

問題を解くときは終了条件を指定しなければならない

コンピュータが関数を連続的に呼び出すと、コンピュータメモリ内のスタックフレームにスタックされます.
したがって、実装ではスタックライブラリではなく再帰関数が一般的に使用される.

DFS

深さ優先ブラウズと呼ばれるアルゴリズムで、グラフィックで深さを優先的にブラウズします.
スタックまたは再帰関数の使用

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

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

実行できなくなるまで2回繰り返します
-サンプルグラフ-少ない数値ノードからアクセスするように設定

[Step 1]先頭ノード1をスタックに挿入してディスパッチする
隣接ノード2、3、8の最小2をスタックに入れてアクセス
アクセスされていない隣接ノード7をスタックに格納し、アクセスを処理する
[Step 4]アクセスしていない隣接ノードの小6をスタックに入れてアクセスする
[Step 5]6をスタックから削除
[Step 6]アクセスしていない隣接ノード8をスタックに入れてアクセスする
繰り返し[Step 7]
アクセス順:1-2-7-6-8-3-4-5

 
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,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]
  visited = [False]*9
  
  dfs(graph, 1, visited)
  

BFS

BFSは幅優先ナビゲーションと呼ばれ,より近いノードから優先的にナビゲーションするアルゴリズムである.
キューデータ構造の使用

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

キューからノードを取り出した後、隣接するすべてのノードからアクセスされていないノードをキューに挿入してアクセス処理を行います.

完了できないまで手順2を繰り返します
-サンプルグラフ-少ない数値ノードからアクセスするように設定

キューに［Step 1］の先頭ノードとしてノードを挿入して、レビューを行います.
[Step 2]キューから1を取り出し、隣接ノード2,3,8をキューに入れてアクセスする
[Step 3]キューから2を取り出し、未アクセスの隣接ノード7をキューに入れてアクセスする
[Step 4]キューから3を取り出し、未アクセスの隣接ノード4,5をキューに入れてアクセスする
繰り返し[Step 5]
アクセス順:1-2-3-8-7-4-5-6

 
from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited) :

	queue = deque([start])
    # 현재 노드를 방문처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue :
    	#큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = '')
        
        #아직 방문하지 않은 인접한 원소들을 큐에 삽입
        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
  
  bfs(graph, 1, visited)