BFS (Breath First Search)

 

BFS는 너비우선탐색 이라고 블리는 Graph 알고리즘 중 하나이다.

 

 - BFS 는 일반적으로 Queue를 이용해 구현

 

 - 시작 정점과 인접한 모든 정점을 방문하는 방법

 

 - 얻어진 해가 최단 경로가 된다는 것을 보장

 

 - 경로가 매우 길 경우에는 많은 저장 Memory 가 필요

 

 

C++를 이용해 BFS를 구현

#include <iostream>
  #include <vector>
  #include <algorithm>

  using namespace std;

  vector<int>* vertex;
  bool* checked;

  void bfs(int st);

  int main() {
      int n, m, s;
      int from, to;
      cin >> n >> m >> s;
      vertex = new vector<int>[n + 1];
      checked = new bool[n + 1];
      for (int i = 0; i < n + 1; i++) checked[i] = false;
      while (m--) {
          cin >> from >> to;
          vertex[from].push_back(to);
          vertex[to].push_back(from);
      }
      for (int i = 0; i < n; i++) sort(vertex[i].begin(), vertex[i].end());
      bfs(s);

      delete[] vertex;
      delete[] checked;

      return 0;
  }

  void bfs(int st) {
  	cout << st << " ";
  	que.push(st);
  	checked[st] = true;
  	while (!que.empty()) {
  		int from = que.front();
  		que.pop();
  		for (int i = 0; i < vertex[from].size(); i++) {
  			if (!checked[vertex[from][i]]) {
  				cout << vertex[from][i] << ' ';
  				checked[vertex[from][i]] = true;
  				que.push(vertex[from][i]);
  			}
  		}
  	}
  }

 

알고리즘 연습문제

 - https://www.acmicpc.net/problem/1260