너비 우선 탐색(BFS, Breadth-First Search)

너비 우선 탐색이란, 임의의 노드 또는 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 

 

구현:

(1) 시작점을 큐에 삽입

(2) 시작점을 색칠, BFS 시작 (while 문)

(3) 큐에서 하나를 뺀다. pop 된 node가 현재 위치!

(4) 인접 노드에 방문 했는지 확인
 - 방문 안했으면, 색칠하고 큐에 삽입

(5) 모두 완료 했으면 (3)으로 돌아간다. 

/*
 
너비우선탐색 (BFS)
 
(1) -----(2) ------(6)
  \     / \       /
   \   /  (4) ---(5)
    \ /   / \
    (3)- (7)-(8)-(9)
    
----------------------------------
DFS : 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9
BFS : 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 5 -> 8 -> 9
9 12
1 2
1 3
2 4
2 6
3 7
4 5
4 7
4 8
5 6
7 8
8 9
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100005
 
vector<int> myGraph[MAX];
queue <int> Queue;
bool visited[MAX];
int n, m;
 
void BFS(){
  // 1. 시작점을 큐에다가 삽입한다.
  // 2. 시작점을 색칠한다.
  
  //BFS 시작!
  
  //Queue.push(x) //큐의 맨뒤에 x원소를 삽입
  //Queue.pop(); //큐의 맨 앞에 있는 원소를 제거
  //Queue.front(); // 맨 앞에 있는 원소를 반환
  //Queue.empty(); // 비어있으면 true를 반환
  
  Queue.push(1);
  visited[1]=true;
  
  while(!Queue.empty()){
    int current = Queue.front();
    Queue.pop();
    cout<<current<<" ";
    
    for(int i = 0; i<myGraph[current].size(); i++){
      int next = myGraph[current][i];
      // current -- next
      
      if(!visited[next]){
        visited[next] = true;
        Queue.push(next);
      }
    }
  }
  
}
 
 
int main(){
  cin>>n>>m;
  for(int i = 0; i<m; i++){
    int a, b;
    cin>>a>>b;
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
    
  }
  
  BFS();
  
  return 0;
}
 
//결과:  0 1 2 3 5 4 6 7 8