BFS (Breadth-First Search)

BFS (Breadth-First Search)

그래프의 한 정점에서 시작하여 인접한 모든 정점을 먼저 방문한 후 다음 레벨로 진행하는 그래프 순회 알고리즘으로, 큐로 구현하며 최단 경로를 보장

목적: 최단 경로(무가중치), 레벨 순회, 연결 요소

특징: 너비 우선, 큐 사용, 레벨별 탐색, 최단 경로 보장(무가중치)

동작

구현: 큐(FIFO) + 방문 배열

시간 복잡도: O(V + E) - 인접 리스트, O(V²) - 인접 행렬

공간 복잡도: O(V) - 큐 + 방문 배열

장점: 최단 경로 보장(무가중치), 레벨별 탐색, 무한 루프 안전(방문 체크)

단점: 메모리 사용 많음(넓은 그래프), 경로 저장 어려움

적용사례

• •최단 경로(무가중치)
• •레벨 순회(트리)
• •연결 요소
• •소셜 네트워크(친구 추천, 거리)
• •웹 크롤러
• •GPS 내비게이션(단순 그래프)

비교: BFS(너비/큐/최단경로/메모리많음) vs DFS(깊이/스택/경로/메모리적음)

연관: 그래프, DFS, 최단 경로, 큐, 레벨 순회