[그래프] BFS(너비우선탐색)

1. 개념

BFS(Breadth First Search)는 그래프 전체를 탐색하는 방법 중의 하나입니다. 그래프 전체를 탐색하는 방법은 크게 BFS와 DFS, 두 가지가 있다고 할 수 있습니다. 그 둘 중 오늘은 BFS에 대해 배워보도록 하겠습니다. 

BFS의 핵심은 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현한다는 점입니다.  

그리고, 이를 구현하기 위해 STL의 queue를 사용하게 됩니다. 

인접한 노드들을 먼저 방문한다는 말이 잘 이해가 안되신다면, 아래의 그림을 통해 이해하실 수 있을 겁니다.

위의 그림은, 노드 A부터 시작해서 BFS로 모든 노드를 방문하는 것을 나타낸 모습입니다. BFS는 인접한 노드들을 차례대로 방문한다고 했었습니다. 시작 노드인 노드 A에 인접한 노드는 노드 B, C, D이므로 차례대로 해당 노드들을 방문해줍니다. 이제 노드 B, C, D에 인접한 노드들을 방문해줘야겠죠? 노드 B에 인접한 노드 E, F와 노드 C에 인접한 노드 G를 방문해주면, 그래프에 존재하는 모든 노드를 방문했기 때문에 전체탐색을 끝마치게 됩니다.

즉, 한 마디로 이렇게 정리할 수 있습니다.

'그래프'를 '시작점을 루트로 하는 트리'라고 생각한다면,

"height가 작은 노드부터 차례대로 방문하는 전체 탐색 방식"

그렇다면 queue를 이용해서 어떻게 위의 그림과 같은 BFS를 구현할 수 있을까요? 

시작점을 queue에 push한 후, 아래의 세 단계를 queue가 빌 때까지 반복해나가는 방식으로 구현해낼 수 있습니다.

① queue의 가장 앞에 있는 노드를 pop 

② 현재 노드에 인접한 모든 노드들 중 아직 방문하지 않은 노드들을 queue에 push

③ queue가 비어있지 않으면, ①번부터 다시 실행

글로만 봐서는 어떤 식으로 동작하는지 이해가 잘 안되실 겁니다. 따라서, 아래의 그래프를 통해 직접 동작하는 원리를 이해해보도록 하겠습니다.

2. 예시

왼쪽의 그래프를 오른쪽의 queue를 이용해, 너비우선탐색 해 보도록 하겠습니다. 

아래의 동작 과정을 쉽게 이해하기 위해선, push와 pop의 의미를 다음과 같이 이해하는 것이 편합니다.

push : 나중에 방문할 노드 저장

pop  : front에 있는 노드 방문

시작점을 노드 A라고 가정했습니다. 그렇다면, 우선 queue에 노드 A를 push해 줘야겠죠? pop하는 것이 front에 있는 노드를 방문하는 것이기 때문에 가장 먼저 방문해줘야하는 노드 A를 push해 주는 것입니다.

그 후 부터는, 위에서 설명한 ①,②,③의 단계를 따라주면 됩니다.

① queue의 가장 앞에 있는 노드(A)를 pop해줍니다.

② 현재 노드(A)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(B,C,D)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(B)를 pop해줍니다.

② 현재 노드(B)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(E,F)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(C)를 pop해줍니다.

② 현재 노드(C)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(G)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(D)를 pop해줍니다.

② 현재 노드(A)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(없음)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(E)를 pop해줍니다.

② 현재 노드(A)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(없음)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(F)를 pop해줍니다.

② 현재 노드(A)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(없음)을 queue에 push 

③ ①번부터 다시 실행

① queue의 가장 앞에 있는 노드(G)를 pop해줍니다.

② 현재 노드(A)에 인접한 모든 노드들 중 아직 방문하지 않은 노드들(없음)을 queue에 push 

③ queue가 비어있으므로, 종료

3. 구현

위의 예시에서, 매번 pop되는 노드들의 순서를 확인해보면, 그 순서가 BFS의 결과라는 것을 알 수가 있습니다. 즉, ①,②,③의 논리 구조를 코드로 구현해내기만 하면, BFS를 구현할 수 있다는 말이 되겠죠? 위의 논리구조를 코드로 간단히 나타내면, 아래와 같이 나타낼 수 있습니다.

while(queue가 비어있지 않은 동안)

{

① queue의 가장 앞에 있는 노드를 pop 

② 현재 노드에 인접한 모든 노드들 중 아직 방문하지 않은 노드들을 queue에 push

}

이 논리구조를 그대로 코드로 구현한 것이 바로 아래의 코드입니다.

#define MAXV 8
 
//그래프의 연결 관계를 인접리스트로 저장
vector<int> adj[MAXV];
//visited[i] : 노드 i를 방문한 적이 있으면 1, 없으면 0
int visited[MAXV];
 
int main()
{
    queue<int> q;
 
    //시작 노드 번호가 1이라고 가정
    int src = 1;
    q.push(src);
    visited[src] = 1;
 
    //queue가 비어있지 않은 동안
    while(!q.empty())
    {
        //① queue의 가장 앞에 있는 노드를 pop 
        int here = q.front();
        q.pop();
 
        //② 현재 노드에 인접한 모든 노드들 중
        for(int i=0; i<adj[here].size(); i++)
        {
            int there = adj[here][i];
            
            // 아직 방문하지 않은 노드들을 queue에 push
            if(visited[there] == 0)
            {
                q.push(there);
                visited[there] = 1;
            }
        }
    }
    
}