깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색 DFS(Depth First Search)와 너비 우선 탐색 BFS(Breadth First Search)은 그래프를 탐색할 때 사용되는 알고리즘이다.

📌그래프란, vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, dege는 정점과 정점을 연결하는 간선이다.

1. 깊이 우선 탐색(DFS)

시작 정점으로부터 최대한 깊이 탐색한 뒤, 더이상 탐색 할 곳이 없을 경우 옆으로 이동

💡깊이 우선 탐색은 루트 노드(혹은 다른 임의의노드)에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완변하게 탐색하는 방법이다.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
즉, 넓게(wide) 탐색전에 깊게(deep) 탐색하는것이다.
모든 노드를 방문 하고자 하는 경우 적합한 방법이다.
너비 우선 탐색(BFS)보다 간단히 구현이 가능하다.
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.

2. 너비 우선 탐색(BFS)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

💡너비 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점은 나중에 방문하는 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 적합한 방법이다.
깊이 우선 탐색(DFS)보다 구현이 조금 더 복잡하다.

3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

깊이 우선 탐색(DFS)	너비 우선 탐색(BFS)
현재 정점에서 최대한 깊숙히 들어가서 탐색한 뒤 다시 돌아가 다른 루트로 탐색하는 방식	현재 정점과 인접한 정점부터 탐색하는 방식
스텍 또는 재귀함수로 구현	큐를 이용해서 구현

4. 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)의 구현

그래프의 구현은 인접 행렬과 인접 리스트 두가지 방법이있다. 아래 구현 예시는 인접 리스트를 사용하였고 DFS, BFS를 통해 방문한 노드의 값을 출력하는 코드이다.

DFS(재귀 함수를 사용해 구현)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
# 방문노드
visited = [False] * len(graph)

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 0번 노드가 없으니 1번 노드부터 탐색
dfs(graph, 1, visited)

BFS(큐를 사용해 구현)

# BFS - 너비 우선 탐색 - 큐(FIFO)를 이용. collections의 deque 이용!
from collections import deque

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)


def bfs(graph, start, visited):
    # 시작 노드를 큐에다가 먼저 삽입(삽입할 때 파이썬 리스트[]로 감싸주기)
    queue = deque([start])
    # 시작 노드를 방문 처리
    visited[start] = True

    # 큐에서 노드를 pop하고 그 노드의 인접노드들을 탐색. 단, 큐가 빌(False)때 까지
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

bfs(graph, 1, visited)

Deeppago's study note