アルゴリズムを理解する前に、資料構造図の概念を熟知してください.
DFSとBFSはブラウズアルゴリズムである.
このアルゴリズムを使用して、グラフィック内のすべてのノードにアクセスできます.

DFS

深度優先探索(Depth Priority Search)は「深度優先探索」とも呼ばれ、グラフィックで深部を優先的に探索するアルゴリズムである.
スタックを利用して実現します.

オペレーションプロセス

文章

①ナビゲーション開始ノードをスタックに挿入してアクセス処理を行う.
②スタックの最上位ノードに未アクセスの隣接ノードがある場合は、スタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
③再実行できなくなるまで2回目の手順を繰り返す.
アクセスされていない隣接ノードが複数ある場合は、スタックに最小サイズの数を入れます.

絵をかく

#0
DFSの動作手順をグラフで説明します.

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

#2
スタックの最上位ノード「1」には、アクセスされていない隣接ノード「2」、「3」、「8」がある.このうち最小のノード「2」をスタックに入れてアクセス処理を行う.

#3
スタックの最上位ノード「2」には、アクセスされていない隣接ノード「7」があります.そこで、スタックに7番ノードを入れてアクセス処理を行います.

#4
スタックの最上位ノード「7」には、アクセスされていない隣接ノード「6」および「8」があります.このうち最小のノード「6」をスタックに入れてアクセス処理を行う.

#5
スタックの最上位ノード「6」には、アクセスされていない隣接ノードはありません.したがって、スタックから6番ノードを取り出します.

#6
スタックの最上位ノード「7」には、アクセスされていない隣接ノード「8」があります.したがって、スタックに8番ノードを入れてアクセス処理を行います.

#7
スタックの最上位ノード「8」には、アクセスされていない隣接ノードはありません.したがって、スタックから「8」番ノードを取り出します.

#8
スタックの最上位ノード「7」にアクセスしていない隣接ノード.したがって、スタックから「7」番ノードを取り出します.

#9
スタックの最上位ノード「2」には、アクセスされていない隣接ノードはありません.したがって、スタックから「2」番ノードを取り出します.

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

#11
スタックの最上位ノード「3」には、アクセスされていない隣接ノード「4」および「5」があります.このうち最小のノード「4」をスタックに入れてアクセス処理を行う.

#12
スタックの最上位ノード「4」には、アクセスされていない隣接ノード「5」があります.そこで、スタックに「5」ノードを入れてアクセス処理を行います.

#13
スタック内の残りのノードには、アクセスされていない隣接ノードはありません.したがって、以下に示すように、すべてのノードを順番に取り出します.

DFSを使用してこの図面にアクセスします.
1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
順番に探索できます.

時間の複雑さ

N個のデータであればO(N)が必要です.

コード#コード#

DFSはスタックを必要とするアルゴリズムであるため,実際の実装は再帰関数を用いて実現できる.

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
# 첫 요소는 인덱스를 1번부터 사용하기 위해 비워두었다.
# 리스트의 인덱스가 노드 번호이며 요소 속 데이터가 해당 노드와 연결된 노드 들이다.
graph = [
    [],			
    [2,3,8],	# 1번 노드 | 2,3,8 노드와 연결됨
    [1,7],	# 2번 노드 | 1,7 노드와 연결됨
    [1,4,5],	# 3번 노드 | 1,4,5 노드와 연결됨
    [3,5],	# 4번 노드 | 3,5 노드와 연결됨
    [3,4],	# 5번 노드 | 3,4 노드와 연결됨
    [7],	# 6번 노드 | 7 노드와 연결됨
    [2,6,8],	# 7번 노드 | 2,6,8 노드와 연결됨
    [1,7]	# 8번 노드 | 1,7 노드와 연결됨
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
# 인덱스를 1번 부터 사용하기 위해 요소가 1개 더 많은 9개이다. 
visited = [False] * 9

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

1 2 7 6 8 3 4 5

BFS

「広さ優先検索」は、「幅優先検索」とも呼ばれ、グラフィックの近い部分を優先的に検索するアルゴリズムです.
キューを使用して実装します.

オペレーションプロセス

文章

①ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
②ノードをキューから取り出し、そのノードの隣接ノードからアクセスしていないノードを全てキューに挿入してアクセス処理を行う.
③再実行できなくなるまで2回目の手順を繰り返す.
複数の隣接ノードがアクセスされていない場合は、キューを最小の順序で挿入します.

絵をかく

#0
DFSの動作手順をグラフで説明します.

#1
開始ノード「1」をキューに挿入し、アクセス処理を行います.アクセス処理のノードはグレー,キューから取り出し,現在処理しているノードは青で表される.

#2
キューから「1」を取り出し、アクセスしていない隣接ノード「2」、「3」、「8」をすべてキューに挿入してアクセス処理を行う.

#3
ノード「2」をキューから取り出し、アクセスしていない隣接ノード「7」をキューに挿入してアクセス処理を行う.

#4
ノード「3」をキューから取り出し、アクセスしていない隣接ノード「4」と「5」をキューに挿入してアクセス処理を行う.

#5
ノード「8」をキューから取り出し、アクセスされていない隣接ノードを無視します.

#6
ノード「7」をキューから取り出し、アクセスしていない隣接ノード「6」をキューに挿入してアクセス処理を行う.

#7
残りのノードには、アクセスされていない隣接ノードはありません.したがって、すべてのノードを順番に取り出すと、最終的には次のようになります.

BFSを使用してこのグラフィックにアクセスします.
1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
順番に探索できます.

時間の複雑さ

N個のデータであればO(N)が必要です.

コード#コード#

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
# 첫 요소는 인덱스를 1번부터 사용하기 위해 비워두었다.
# 리스트의 인덱스가 노드 번호이며 요소 속 데이터가 해당 노드와 연결된 노드 들이다.
graph = [
    [],			
    [2,3,8],	# 1번 노드 | 2,3,8 노드와 연결됨
    [1,7],	# 2번 노드 | 1,7 노드와 연결됨
    [1,4,5],	# 3번 노드 | 1,4,5 노드와 연결됨
    [3,5],	# 4번 노드 | 3,5 노드와 연결됨
    [3,4],	# 5번 노드 | 3,4 노드와 연결됨
    [7],	# 6번 노드 | 7 노드와 연결됨
    [2,6,8],	# 7번 노드 | 2,6,8 노드와 연결됨
    [1,7]	# 8번 노드 | 1,7 노드와 연결됨
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
# 인덱스를 1번 부터 사용하기 위해 요소가 1개 더 많은 9개이다. 
visited = [False] * 9

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

1 2 3 8 7 4 5 6

BFS DFSの比較

進行方法

DFS-は1つの頂点からできるだけ深く入り込み、頂点に移行します.
BFS-現在の頂点に最も近い頂点に移動します.
例えば、10単位ごとの国語、英語、数学の試験を勉強するとき
DFSは第10節の国語を終えた上で英語の勉強を始めた.
BFSは、まず国語、英語、数学の1単位を学び、それから国語、英語、数学の2単位を学ぶように表現することができる.

スピード

速度はBFSの方が速い.しかし,各アルゴリズム問題には適切な役割がある.

使用方法

グラフィックのすべての頂点にアクセスすることが重要な問題→DFS、BFS

経路特徴を記憶する必要がある問題→DFS

最短距離で解く問題→BFS

検索したパターンが本当に大きい場合→DFS、(BFS)

検索対象の規模が大きくなく、検索起点から遠くない→BFS、(DFS)

参考資料

就職のためのコードテストとPythonと羅東彬
幅優先ナビゲーション-ツリーウィキ
DFS、BFS説明、区別-luck-korma