Algorithm Guidecomplexity: O(V+E)

너비 우선 탐색 (BFS)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Breadth-First Search

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

Logic Node1 / 9

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

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