BFS(Breadth-First Search, 너비 우선 탐색)는 그래프의 시작 정점에서 가까운 정점부터 차례로 탐색하는 알고리즘이다. 큐를 사용하며, 최단 경로(비가중치 그래프) 탐색의 표준 알고리즘이다.
동작 원리
그래프: 1 - 2 - 5
| |
3 - 4
시작: 1
큐: [1] → [2, 3] → [3, 5, 4] → [5, 4] → [4] → []
방문 순서: 1 → 2 → 3 → 5 → 4
구현
python
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
graph = {1:[2,3], 2:[1,5,4], 3:[1,4], 4:[2,3], 5:[2]}
print(bfs(graph, 1)) # [1, 2, 3, 5, 4]
최단 경로 (비가중치)
python
def bfs_shortest(graph, start, end):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == end:
return path
for n in graph[node]:
if n not in visited:
visited.add(n)
queue.append((n, path + [n]))
return None
시간 복잡도
- •O(V + E): V=정점 수, E=간선 수
BFS vs DFS
| 항목 | BFS | DFS |
|---|
| 자료구조 | 큐 | 스택/재귀 |
| 최단 경로 | ✓ (비가중치) | ✗ |
| 메모리 | 더 많음 | 적음 |
| 활용 | 최단 경로, 레벨 탐색 | 연결 요소, 위상 정렬 |
관련 개념
- •그래프 — 탐색 대상 자료구조
- •큐 — BFS의 핵심 자료구조
- •다익스트라 — 가중치 그래프 최단 경로
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 22
