[Algorithm] BFS 알고리즘 (Breadth-First Search)

너비 우선탐색 (BFS)란?

BFS는 그래프 전체를 탐색하는 방법 중 하나로써 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색합니다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다. 주로 구현은 큐라는 자료에 이웃하는 정점을 다 담아놓고 차례대로 POP을 하는 방식으로 구현합니다.

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

BFS의 장점

1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.

2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
3.너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
4. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

 

BFS의 단점

1. 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

 

 간단한 BFS 구현 (C / C++) 

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 1050;
int n,m;
vector<int> v[MAX];
bool check_bfs[MAX];

void BFS(){
  queue<int> q; //Queue 생성
  q.push(0); //초기 시작점 저장
  check_bfs[0] = true; //초기 방문 체크
  
  while(!q.empty()){
    int current = q.front();
    q.pop();
    printf("%d ",current);
    
    for(int i=0;i<v[current].size();i++){
      int next = v[current][i];
      
      if(!check_bfs[next]){
        check_bfs[next] = true;
        q.push(next);
      }
    }
  }
}

int main() {

  scanf("%d %d",&n,&m);
  
  //그래프 노드 관계 설정
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    
    v[a].push_back(b);
    v[b].push_back(a);
  }
  
  BFS();
  return 0;
}