Algorithm Guidecomplexity: O(V+E)

너비 우선 탐색 (BFS)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Breadth-First Search

목표G

현재—

깊이—

상태대기

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 파이썬 구현 코드

너비 우선 탐색 (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

Guide Progress0%