BFS & DFS
BFS (Breadth First Search)
너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다.
BFS는 큐(Queue) 자료구조를 이용하며, 동작 방식은 다음과 같다.
- 탐색시작 노드를 큐에 저장(q.push()) 후 *방문 처리
- 큐에서 노드를 꺼내(q.pop()) 해당 노드의 인접 노드들을 큐에 저장 후 방문 처리
- 큐가 빌 때까지 반복
여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것을 의미
BFS 동작 과정
1) 시작 노드인 노드 1을 큐에 삽입하고 방문 처리
2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 방문 처리
3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 방문 처리
(일반적으로 인접한 노드가 2개 이상인 경우에는 해당 노드들 중 번호가 낮은 노드부터 처리)
4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 방문 처리
5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 방문 처리
6) 그래프 내 노드에서 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼냄
결과적으로 노드의 탐색 순서, 즉 큐에 삽입한 순서는 다음과 같다.
1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7
BFS 구현 코드
# deque 라이브러리 불러오기
from collections import deque
# BFS 메서드 정의
def bfs (graph, node, visited):
# 큐 구현을 위한 deque 라이브러리 활용
queue = deque([node])
# 현재 노드를 방문 처리
visited[node] = True
# 큐가 완전히 빌 때까지 반복
while queue:
# 큐에 삽입된 순서대로 노드 하나 꺼내기
v = queue.popleft()
# 탐색 순서 출력
print(v, end = ' ')
# 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
for i in graph[v]:
if not (visited[i]):
queue.append(i)
visited[i] = True
DFS (Depth First Search)
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조를 이용하며, 동작 방식은 다음과 같다.
- 현재 노드 방문처리
- 현재 노드와 연결된 다른 노드들 방문
- 해당 노드를 방문하지 않았다면 재귀적으로 dfs 함수 실행
DFS 동작 과정
1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리
2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있음. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리
3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리
4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽입하고 방문 처리
5) 스택 내 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드 7을 스택에 삽입하고 방문 처리
6) 최상단 노드인 노드 7에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 7을 꺼냄
7) 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 6을 꺼냄
8) 마찬가지로 노드 8, 2도 위와 같은 과정을 거친 후, 노드 1에 인접하면서 방문 이력이 없는 노드 3을 스택에 삽입하고 방문 처리
9) 노드 3에 인접하면서 방문하지 않은 노드는 노드 4와 5가 있지만, 번호가 낮은 노드 4를 스택에 삽입하고 방문 처리
10) 노드 4에 인접한 노드 5를 스택에 넣고 방문 처리
11) 방문하지 않은 노드가 없기 때문에 스택에서 모든 노드를 차례대로 꺼냄
결과적으로 노드의 탐색 순서, 즉 스택에 삽입한 순서는 다음과 같다.
1 -> 2 -> 8 -> 6 -> 7 -> 3 -> 4 -> 5
DFS 구현 코드
# DFS 메서드 정의
def dfs (graph, node, visited):
# 해당 노드를 방문 처리
visited[node] = True
# 탐색 순서 출력
print(node, end = ' ')
# 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리
for i in graph[node]:
if not visited[i]:
dfs(graph, i, visited)