너비 우선 탐색 (breadth-first search (BFS))

한 줄 정의: 시작 정점으로부터 가까운 정점들을 거리 단계별로 차례차례 방문하는 그래프 탐색 알고리즘으로, 큐 자료구조를 이용해 구현된다.

쉽게 풀면

너비 우선 탐색은 시작점에서 한 걸음 거리에 있는 모든 정점을 먼저 방문하고, 그다음 두 걸음 거리에 있는 정점들을 방문하는 식으로 물결이 퍼지듯 탐색을 진행한다. 마치 연못에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가는 모습과 비슷하다. 모든 간선의 가중치가 같다고 가정할 때, 이 방식으로 탐색하면 출발점에서 각 정점까지의 최단 거리를 자연스럽게 구할 수 있다.

왜 중요한가

너비 우선 탐색은 그래프 탐색의 가장 기본적인 도구이면서도, 최단 경로·연결성 판단·레벨별 그룹화가 필요한 다양한 문제의 토대가 된다. 소셜 네트워크 분석, 웹 크롤링, 네트워크 라우팅, 게임 트리 탐색 등 그래프로 모델링되는 거의 모든 실무 문제에서 기본 서브루틴으로 등장하기 때문에, 관련 논문들이 새로운 방법론을 설명할 때 비교 기준선(baseline)이나 전처리 단계로 자주 인용한다. 특히 대규모 그래프를 다루는 분산 컴퓨팅·그래프 신경망 연구에서는 BFS의 병렬화·확장성 자체가 독립적인 연구 주제로 다뤄지기도 한다.

논문에서는 이렇게 쓰입니다

"소셜 네트워크에서 두 사용자 간의 최단 연결 단계를 구하기 위해 너비 우선 탐색을 적용하였다."

가중치가 없는 그래프에서의 최단 경로 탐색이나 레벨별 탐색이 필요한 문제에서 사용된다.

"제안하는 그래프 신경망은 각 노드의 k-hop 이웃 정보를 수집하기 위해 너비 우선 탐색 기반의 샘플링 전략을 채택하였다."

그래프 신경망 연구에서는 노드 주변의 이웃 범위를 정의하고 메시지 전달(message passing)에 사용할 노드 집합을 구성할 때 BFS의 레벨 개념이 활용된다.

"대용량 웹 그래프에서 연결 요소를 식별하기 위해 병렬 너비 우선 탐색 알고리즘을 사용하였으며, 기존 순차 처리 방식 대비 처리 시간이 크게 단축되었다."

대규모 분산 시스템 분야에서는 BFS 자체를 여러 노드에 나누어 병렬로 수행하는 방법이 성능 개선의 핵심 주제로 다루어진다.

조금 더 깊게 보면

BFS를 논문에서 접할 때는 시간 복잡도가 정점 수와 간선 수에 비례하는 O(V+E) 형태로 표현된다는 점, 그리고 방문 여부를 표시하는 자료구조와 큐의 구현 방식에 따라 실제 성능이 달라질 수 있다는 점을 함께 알아두면 이해가 쉽다. 그래프 신경망 맥락에서는 BFS로 정의되는 'k-hop 이웃'이 곧 모델이 정보를 집계하는 범위(receptive field)와 직결되므로, 몇 단계까지 탐색할지가 모델 설계의 중요한 선택지가 된다. 또한 대규모 그래프에서는 순수 BFS 대신 일부 이웃만 샘플링하거나 여러 프로세서에 탐색을 분산시키는 변형 기법이 흔히 함께 언급된다.

주의할 점

너비 우선 탐색은 모든 간선의 가중치가 동일하다고 가정할 때만 최단 경로를 보장하며, 가중치가 다른 그래프에서는 다익스트라 알고리즘 등을 사용해야 한다.