Algorithm Guidecomplexity: O(V+E)

너비 우선 탐색 (BFS)

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

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

잔잔한 물에 돌을 던졌을 때 동심원이 퍼지듯, 가까운 곳부터 훑는 것.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 너비 우선 탐색 (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