Algorithm Guidecomplexity: O(V+E)

너비 우선 탐색 (BFS)

Queue(FIFO)를 사용해 가까운 노드부터 층층이(level-order) 확장하는 그래프 탐색 알고리즘입니다. 무가중치 그래프에서 최단 경로를 보장하며, 최단 거리·컴포넌트 탐지·위상 정렬의 기반이 됩니다.

01너비 우선 탐색 (BFS)

알고리즘 작동 원리 탐색

BFS 시작. 큐(FIFO)로 가까운 노드부터 층층이 확장해 목표 G까지의 최단 경로를 찾습니다.

A를 꺼내 확장합니다. 이웃 B, C를 큐 뒤쪽에 추가하고 방문 표시합니다.

B를 꺼내 확장합니다. 이웃 D, E를 큐에 추가합니다(A는 이미 방문했으므로 건너뜁니다).

C를 꺼내 확장합니다. 이웃 F, G를 큐에 추가합니다. G는 목표지만, BFS는 꺼낼 때 검사하므로 일단 큐에 넣습니다.

D를 꺼냅니다. 리프 노드라 추가할 이웃이 없습니다. 방문 처리 후 다음 노드로 넘어갑니다.

E를 꺼내 확장합니다. 이웃 H를 큐에 추가합니다.

F를 꺼냅니다. 이웃 H는 이미 큐에 있으므로 건너뜁니다.

G를 꺼냅니다. 목표와 일치 — BFS가 최단 경로 A → C → G (깊이 2)로 도달했습니다.

탐색 완료 · 최단 경로 A → C → G (비용 2). 탐색한 노드는 7개, 무가중치 그래프의 최단 경로를 보장합니다.

Live Python

1def bfs(graph, start, target):

# queue = [A]

2 queue = deque([start])

3 parent = {start: None}

# visited = {A}

4 visited = {start}

5 while queue:

6 current = queue.popleft()

7 for nb in graph[current]:

8 if nb not in visited:

9 visited.add(nb)

10 parent[nb] = current

11 if nb == target:

12 return reconstruct(parent, target)

13 queue.append(nb)

14 return None

1 / 9

02 쉽게 이해하기

For Everyone

🔑핵심 동작

출발점에서 가까운 정점부터 층층이 방문합니다. 간선에 가중치가 없으면 이 순서가 곧 최단 경로입니다.

💡쉽게 말하면

큐로 가까운 노드부터 층층이 방문합니다.

가중치 없는 그래프에서 최단 경로를 보장해요.

📍어디에 쓰나

–최단 경로(무가중치)
–친구 추천
–미로 최단거리

03 파이썬 구현 코드

너비 우선 탐색 (BFS)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

from collections import deque

def bfs(graph, start, target):
    queue = deque([start])
    parent = {start: None}
    visited = {start}
    while queue:
        current = queue.popleft()
        for nb in graph[current]:
            if nb not in visited:
                visited.add(nb)
                parent[nb] = current
                if nb == target:
                    return reconstruct(parent, target)
                queue.append(nb)
    return None