[알고리즘] 그래프 순회 문제 - 2. 너비 우선 탐색(BFS)

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다.

 

깊이 우선 탐색(DFS) 보러가기

2.2.3 너비 우선 탐색 ; Breadth-First Search

너비 우선 탐색(BFS)은 시작 정점과 가까운 정점부터 반복적으로 탐색해나가는 방식을 의미한다. 

그래프 예시

다음과 같은 모양의 그래프가 있다고 가정한다. 0번째 정점을 시작으로 작은 값부터 찾아간다고 가정했을 때, BFS 알고리즘을 적용하면 다음과 같은 순서로 진행된다.

1단계 : 0번 정점 방문

2단계 : 0번 정점과 인접한 정점 중 가장 값이 작은 1번 정점 방문

3단계 : 0번 정점과 인접한 정점 중 방문하지 않았고, 가장 값이 작은 2번 정점 방문

4단계 : 0번 정점과 인접한 정점 중 방문하지 않은 3번 정점 방문

5단계 : 0번 정점과 인접한 정점들을 모두 방문하였으므로 다음 정점인 1번 정점을 기준으로 함. 1번 정점과 인접한 정점 중 방문하지 않았고, 가장 값이 작은 4번 정점 방문

6단계 : 1번 정점과 인접한 정점 중 방문하지 않은 5번 정점 방문

7단계 : 1번과 2번 정점의 인접한 정점들을 모두 방문하였으므로 3번 정점으로부터 인접한 정점들을 찾음. 3번 정점과 인접한 정점 중 방문하지 않은 6번 정점 방문. 더이상 방문할 수 있는 정점이 존재하지 않으므로 BFS 종료.

따라서 위의 그래프를 DFS를 통해 순회하였을 때 0 ➡️ 1 ➡️ 2 ➡️ 3 ➡️ 4 ➡️ 5 ➡️ 6 순서로 방문한다.

 

2.2.4 너비 우선 탐색 코드

너비 우선 탐색을 구현하는 데는 DFS와 달리 큐를 사용한다. 큐를 이용하여 시작 정점에 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 한다. 정점과 간선 정보가 담긴 1차원 정수 배열 벡터 graph와 방문 여부를 표시하는 bool 벡터 visited를 이용하여, 방문할 정점을 선택한 뒤 BFS를 실행한다. 큐인 q에 시작 정점 정보를 넣은 후 q가 빈 큐가 될 때 까지 반복적으로 탐색을 해 나간다. 시간 복잡도는 O(V + E) (V : 정점의 개수, E : 간선의 개수)로 DFS와 동일하다.

시작 정점과 가까운 정점을 찾는 데 유리하고, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.

void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int vertex = q.front();
        q.pop();
        printf("%d ", vertex);
        for(int i = 0; i < graph[vertex].size(); i++) {
            int next = graph[vertex][i];
            if(!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

위의 함수를 이용한 전체 코드는 다음과 같다. 정점과 간선 입력 방식은 백준 1260번 DFS와 BFS를 이용하였다.

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 1001

using namespace std;

vector<int> graph[MAX];
vector<bool> visited(MAX, false);

void BFS(int vertex);

int main(void) {
    int v, e, start;
    scanf("%d %d %d", &v, &e, &start);

    visited.resize(e + 1);
    
    for(int i = 0; i < e; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    BFS(start);
    return 0;
}

void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int vertex = q.front();
        q.pop();
        printf("%d ", vertex);
        for(int i = 0; i < graph[vertex].size(); i++) {
            int next = graph[vertex][i];
            if(!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}