토픽 25 / 82

BFS (Breadth-First Search)

그래프의 한 정점에서 인접한 모든 정점을 먼저 방문한 후 다음 레벨로 진행하는 그래프 순회 알고리즘

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

특징: 너비 우선, 큐, 레벨별 탐색, 최단 경로 보장

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

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

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

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

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

적용사례: 최단 경로(무가중치), 레벨 순회, 연결 요소, 소셜 네트워크, 웹 크롤러, GPS(단순)

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

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