GRAPH
너비 우선 탐색 (BFS)
큐(Queue)를 이용해 시작 노드에서 가까운 노드부터 한 층씩 넓게 방문하는 과정을 한 단계씩, 또는 자동 재생으로 직접 확인하세요. 시작 노드를 바꿔가며 방문 순서가 어떻게 달라지는지 비교할 수 있습니다.
인접 노드는 항상 알파벳 순서로 방문합니다 — 같은 그래프에서 시작 노드만 바꿔가며 층(레벨)이 달라지는 것을 확인해보세요.
방문 순서 아직 없음
재생 버튼을 눌러 탐색을 시작하세요.
방문 0 / 9 · 간선 확인 0회
1 / 1
PSEUDOCODE
queue ← [start], visited ← {start}while queue not empty u ← queue.dequeue() for each neighbor v of u if v ∉ visited: visited.add(v); queue.enqueue(v)어떻게 동작하나요
시작 노드를 큐에 넣고 방문 표시한 뒤, 큐가 빌 때까지 맨 앞 노드를 꺼내 그 이웃들을 확인합니다. 아직 방문하지 않은 이웃은 방문 표시하고 큐의 맨 뒤에 넣습니다. 큐는 먼저 들어간 노드가 먼저 나오므로(FIFO), 시작 노드에서 가까운 노드(1칸 거리)를 모두 방문한 뒤에야 그다음 거리(2칸)로 넘어갑니다 — 그래서 "층(레벨)" 단위로 넓게 퍼지는 모양이 됩니다.
시간·공간 복잡도
- 시간 복잡도
- O(V + E)
- 공간 복잡도
- O(V)
- 방문 범위
- 도달 가능한 노드만
- 특징
- 최단 거리(칸 수) 보장
V=노드 수, E=간선 수. 가중치 없는 그래프에서 BFS는 시작 노드로부터의 최단 경로(칸 수 기준)를 그대로 보장합니다 — 같은 그래프의 DFS와 방문 순서를 비교해보세요.
같은 그래프를 깊이 우선으로 탐색하면 순서가 완전히 달라집니다 — 깊이 우선 탐색(DFS) 보기 · Algorithm 코스로 돌아가기