그래프 - BFS

BFS란

BFS 너비 우선 탐색이란 그래프의 탐색 알고리즘 중 한 가지이다. 너비 우선 탐색은 깊이 우선 탐색과 그래프 탐색 방식의 두 축을 이루는데, 깊이 우선 탐색이 더 이상 경로가 없을 때 까지 계속 한 방향으로 들어가는 것과 달리 시작점과 가까운 노드부터 탐색하는 방식이다.

BFS의 구현

너비 우선 탐색 과정 중 새로운 노드를 발견하면 그 노드는 시작점과 더 가까이 있는, 더 먼저 발견된 노드보다 먼저 실행 되서는 안된다. 이를 구현하기 위해 BFS는 큐를 사용한다. BFS의 시간 복잡도는 모든 정점을 한 번씩 방문하고 그 때마다 모든 간선을 검사하기 때문에 V+E이다.

최단 거리 알고리즘

BFS의 대표적인 응용 사례는 그래프에서 노드들 사이의 최단 거리를 구하는 알고리즘이다.
BFS를 통해 최단 거리를 구하는 과정은, BFS 과정에서 새로운 간선 (u,v) 이 추가 되어 새로운 노드 v 에 접근할 수 있게 되었을 때, 노드 v까지 가는 최단 거리는 u까지의 최단거리에 간선 (u,v)의 가중치를 더한 것이라는 개념에서 출발한다.
이 과정은 그리디 알고리즘의 방식과 유사한데, 현재 가지고 있는 정보에서 가장 짧은 경로를 최단 거리로 설정하면서 탐색해 나가면 결국 모든 노드에 대한 최단 거리를 구할 수 있게 되는 것이다.