[알고리즘] BFS(너비 우선 탐색)

BFS는 시작 지점을 기준으로 거리(몇번을 거쳐야 하는지)가 짧은 순으로 탐색한다.

BFS는 큐를 이용해 구현할 수 있다.

 

void BFS(int here)
{
    queue<int> q;
    q.push(here);
    discovered[here] = true;
    
    while(q.empty() == false)
    {
    	here = q.front();
        q.pop();
        
        for(int there : adjacent[here]) //큐에 현재 정점과 인접한 정점 중 발견되지 않은 정점을 큐에 예약
        {
		if(discovered[there])
            		continue;
          	  q.push(there);
    		  discovered[there] = true;
         }
     }
 }

 

visited가 아니라 discovered를 사용하는 이유는 방문한 정점만 저장하는 것이 아니라

큐에 push하는 정점들을 모두 true로 check하기 때문에 discovered를 사용한다.