너비 우선 탐색
너비 우선 탐색 (Breadth-First Search, BFS) 은 그래프 탐색 알고리즘의 하나로, 시작 정점에서 가까운 정점부터 차례대로 방문하는 방식이다. 이 알고리즘은 큐 (Queue) 자료구조를 사용하여 구현되며, 특정 정점에서 연결된 모든 이웃 정점을 먼저 방문하고, 그 이웃 정점들의 이웃 정점을 방문하는 방식으로 탐색을 진행한다.
작동 방식:
- 탐색을 시작할 정점을 큐에 넣는다.
- 큐가 비어있지 않은 동안 다음을 반복한다.
- 큐에서 정점을 하나 꺼낸다 (방문한다).
- 꺼낸 정점과 연결된 아직 방문하지 않은 모든 이웃 정점을 큐에 넣는다.
특징:
- 최단 경로 탐색: 너비 우선 탐색은 가중치가 없는 그래프에서 시작 정점으로부터 다른 정점까지의 최단 경로를 찾는 데 유용하다.
- 모든 경로 탐색 불가: 깊이 우선 탐색과는 달리, 시작 정점에서 도달 가능한 모든 정점을 방문하지만, 특정 조건을 만족하는 '모든 경로'를 탐색하는 데는 적합하지 않다.
- 메모리 사용량: 깊이 우선 탐색에 비해 메모리 사용량이 많을 수 있다. 이는 탐색해야 할 노드를 큐에 저장해야 하기 때문이다. 최악의 경우, 그래프의 모든 노드를 저장해야 할 수도 있다.
활용:
- 최단 경로 찾기 (가중치가 없는 그래프)
- 네트워크 브로드캐스트
- 소셜 네트워크에서 친구 관계 탐색
- 웹 크롤러
구현:
너비 우선 탐색은 큐 자료구조를 사용하여 구현되며, 일반적으로 방문한 정점을 기록하기 위해 boolean 배열이나 set 자료구조를 사용한다. 이를 통해 중복 방문을 방지하고 무한 루프를 방지할 수 있다.
장점:
- 최단 경로를 보장한다 (가중치가 없는 그래프).
- 해결책이 존재한다면, 반드시 찾을 수 있다.
단점:
- 깊이 우선 탐색에 비해 메모리 사용량이 많을 수 있다.
- 해 공간이 넓은 경우, 탐색 시간이 오래 걸릴 수 있다.