DFS/BFS

탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

 

 DFS (Depth-First Search) 

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

• 깊이 우선 탐색 : 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀함수)를 이용
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
  3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  4. 더 이상 2단계의 과정을 수행할 수 없을때 까지 반복

 

DFS 동작 예시

[Step 0] 그래프를 준비 (방문 기준: 번호가 낮은 인접 노드부터)

⇒ 시작 노드: 1

https://www.youtube.com/watch?v=7C9RgOcvkvo

[Step 1] 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리

[Step 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드는 ‘2’ ‘3’ ‘8’이다.

⇒ 이 중 가장 작은 노드인 ‘2’를 스택에 삽입하고 방문 처리

[Step 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드는 ‘7’

⇒ ‘7’번 노드를 스택에 넣고 방문 처리

[Step 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘6’ ‘8’

⇒ 그 중 가장 작은 노드 ‘6’을 스택에 넣고 방문 처리

이렇게 깊게 들어갔다가 더 이상 들어갈 수 없다면 다시 돌아와서 다른 방향으로 깊게 들어가는 방식

[Step 5] 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접 노드가 없음

⇒ 따라서 스택에서 ‘6’번 노드를 꺼냄

[Step 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드는 ‘8’

⇒ ‘8’번 노드를 스택에 넣고 방문 처리

이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다.

# DFS 메서드 정의
def dfs(graph, v, visited): # v는 시작 노드
	# 현재 노드 방문 처리
	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 (Breadth-First Search)

• 너비 우선 탐색 : 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 더 이상 2단계의 과정을 수행할 수 없을 때까지 반복

 

[Step 0] 그래프 방문 기준: 번호가 낮은 인접 노드부터

⇒ 시작 노드: 1

[Step 1] 시작 노드인 ‘1’을 큐에 삽입하고 방문 처리

[Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하고 방문 처리

[Step 3] 큐에서 노드 ‘2’를 꺼내 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리

(1은 이미 방문 처리 되어 있음)

[Step 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접 노드 ‘4’ ‘5’를 큐에 삽입하고 방문 처리

[Step 5] 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시

이러한 과정을 반복하여 전체 노드의 탐색 순서(큐에 들어간 순서)는 다음과 같다

1번 노드와의 거리가 1인 것을 먼저 방문

1번 노드와의 거리가 2인 것이 그 다음

각 간선의 비용이 모두 동일한 상황에서 최단 거리 문제를 해결하기 위한 목적일 때 사용한다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	
	# 현재 노드 방문 처리
	visited[start] = True
	
	# 큐가 빌 때 까지 반복
	while queue:
		# 큐에서 넣은 순서대로 원소 하나 뽑아 출력
		v = queue.popleft()
		# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
		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]

 

---

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없다.
• 경로의 특징을 저장해둬야 하는 문제
  각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못함)
• 검색 대상 그래프가 정말 큰 문제
  DFS 사용
• 최단거리 구해야 하는 문제
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
  왜냐하면 DFS으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않은 문제
  BFS 사용