Python 너비 우선 탐색 BFS
BFS는 큐를 사용해 가까운 이웃부터 방문합니다.
너비 우선 탐색 BFS이란?
BFS는 큐를 사용해 가까운 이웃부터 방문합니다.
그래프를 레벨 순서로 탐색합니다.
언제 사용하나요?
- 알고리즘과 자료 구조를 이해합니다.
- 각 단계와 경계 조건을 확인합니다.
- 실행 시간과 메모리 사용량을 비교합니다.
Python 너비 우선 탐색 BFS 시각화
O(V+E)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)예상 출력
['A', 'B', 'C', 'D', 'E']작동 원리
visited가 재방문을 막으며 시간 O(V+E), 메모리 O(V)입니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.
- 빈 입력, 한 요소, 중복값을 시험하세요.
- 각 단계의 상태를 출력하세요.
- 다른 풀이와 성능을 비교하세요.