DFS & BFS

그래프를 탐색하는 방법인 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)에 대해 알아보자.

그래프 탐색이란 하나의 시작점 정점(node)에서 시작하여 차례대로 연결된 정점들을 모두 방문하는 것을 말한다.

 

DFS (Depth-First Search)

DFS는 깊이 우선 탐색이라고도 부르면, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

DFS 동작 예시

출처 : https://developer-mac.tistory.com/64

DFS는 루트 노드에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

 

 

DFS 소스코드 예제 (Python)

# 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차원 리스트)
graph = [
    [],
    [2,3,8], # 1번 노드와 연결
    [1,7], # 2번 노드와 연결
    [1,4,5], # ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

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

# 실행 결과
1 2 7 6 8 3 4 5

 

 

BFS(Breadth-First Search)

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

DFS 동작 예시

출처 : https://devuna.tistory.com/32

DFS는 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로, 루트 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법이다.

ex) 두 노드 사이의 최단 경로를 찾고 싶을 때

 

BFS 소스코드 예제 (Python)

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차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

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

# 실행 결과
1 2 3 8 7 4 5 6

 

 

DFS와 BFS를 활용한 문제 유형/응용

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제(DFS, BFS)
2. 경로의 특징을 저장해둬야 하는 문제(DFS)
3. 최단거리를 구해야 하는 문제(BFS)
4. 검색 대상 그래프가 정말 크다면 DFS 고려
5. 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 멀지 않다면 BFS

 

 

 

 

 

참고 강의 :

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 

참고 블로그 :

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)