10-2. BFS (Breadth-First Search)

10-2. BFS (Breadth-First Search)

1. BFS란?

Breadth-First Search: 너비 우선 탐색

• DFS가 “한 방향으로 끝까지 파고들었다면”,
• BFS는 가까운 노드부터 차례차례 넓게 탐색

💡 동작 방식

예시 그래프:

graph = {
	1: [2, 3],
	2: [4],
	3: [5],
	4: [],
	5: []
}

    1
   / \
  2   3
 /     \
4       5

1 → 2 → 3 → 4 → 5

→ 즉, 레벨 단위로 퍼져나감

---

2. BFS 기본 구조

from collections import deque

def bfs(start):
	queue = deque([start])
	visited[start] = True

	while queue:
		v = visited.popleft()
		print(v, end=' ')

		for neighbor in graph[v]:
			if not visited[neighbor]:
				visited[neighbor] = True
				queue.append(neighbor)

---

3. DFS vs BFS 차이

항목	DFS	BFS
구조	재귀/스택	큐
방향	깊이 우선	너비 우선
최단거리	❌ 보장 안함	✅ 보장
백트래킹 용도	적합	부적합
탐색 순서	깊이 → 깊이	레벨 → 레벨

---

4. BFS 예제 1 – 기본 그래프 순회

from collections import deque

def bfs(start):
	queue = deque([start])	
	visited[start] = True

	while queue:
		v = queue.popleft()
		print(v, end = ' ')
		for neighbor in graph[v]:
			if not visited[neighbor]:
				visited[neighbor] = True
				queue.append(neighbor)
	return


graph = {
	1: [2, 3],
	2: [4, 5],
	3: [],
	4: [],
	5: []
}
'''
    1
   / \
  2   3
 / \    
4   5     
'''

visited = [False] * 6

bfs(1)



''' 출력
1 2 3 4 5
'''

---

5. BFS 핵심 개념 요약

항목	설명
탐색 방식	가까운 곳부터 탐색
자료구조	큐 (Queue) 사용
방문 순서	레벨 순서 (거리 기준)
구현 난이도	DFS보다 약간 복잡하지만 안전함 (스택 오버플로우 없음)
용도	최단거리 탐색, 거리 측정, 경로 복원 등