BFS

루트노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

(인접한 노드 =⇒ 가까운 곳부터 먼저 간다)

 

Queue 를 사용해서 구현할 수 있다.

 

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.

 

시간 복잡도 : O(N+E) ⇒ O(정점개수+간선개수)

 

• 다음 노드를 이미 방문했는지, 방문하지 않았는지를 기록해두는 배열이 필요하다.

bool visit[50] : 기본값 false이므로 방문하면 true로 바꿔준다.

큐에 넣는 순간 visit을 true로 바꾸어주어야한다.

(색칠된 곳은 visit[ ]=true)

BFS 동작 과정

void bfs(){
	vector<bool> visited(N, false);
    queue<int> q;
    
    //q에 push와 visited true체크는 한 세트처럼
    q.push(0); //0에서 시작
    visited[0]=true; //0 방문 처리
    
    while(!q.empty()){
    	int curr = q.front();
        q.pop();
        for(int next : adj[curr]){
        	if(!visited[next]){
            	visited[next]=true;
                q.push(next);
            }
        }
    }
 }