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

깊이 우선 탐색(DFS)과 함께 가장 많이 사용되는 탐색 알고리즘으로, 다익스트라 알고리즘이나 최소 스패닝 트리 알고리즘 등의 기본이 되는 알고리즘.

BFS알고리즘은 시작점에서 가까운 정점부터 순서대로 방문한다.

 

BFS의 탐색 방법

 

BFS알고리즘의 경우엔 각 정점을 방문할 때마다 모든 인접한 정점들을 검사하고, 이중 아직 방문하지 않은 정점이 있는 경우 그 정점을 방문할 예정이라고 저장해둔다.

하나의 정점에 대해 모든 인접한 정점을 검사한 후에는 저장해둔 방문예정인 목록에서 다음 정점을 뽑아서 동일하게 그 정점의 인접한 정점을 검사하는 것을 반복한다. 

그렇기 때문에 BFS에서 방문 순서는 정점의 목록에서 어떤 정점을 먼저 뽑는지에 의해 결정된다.

 

위의 그림의 예시에서 보면 시작점 a를 방문하고 나면 인접한 정점이 추가되는 목록에는 [b, e, c]가 추가된다.

b, c, d는 모두 a와 하나의 간선으로 연결되어 있어서, 셋중 아무거나 먼저 뽑아서 검사해도 된다.

여기서 b를 먼저 뽑아서 검사한다고 가정하면, 목록엔 [e, c, d]가 있게 된다.

그 다음 탐색할 정점은 이전과 달리 아무거나 뽑아도 되는 것이 아니다. d는 두개의 간선을 거쳐야 하기 때문에 d는 e, c가 방문되기 전에 방문되어서는 안된다.

따라서 BFS알고리즘을 구현에 있어서 방문할 정점 목록을 저장하는 데에는 선입 선출(FIFO)방식인 큐를 사용하는 것이 적합하다. 

 

 

BFS의 경우에는 DFS와 달리 정점을 발견한 직후 바로 방문하지 않고 목록에 넣어둔 뒤 목록의 순서대로 방문하게 된다.

결과적으로 [아직 발견되지 않은 상태 -> 발견되었지만 방문되지는 않은 상태 -> 방문된 상태] 의 순서를 거치게 된다.

 

 

BFS의 시간복잡도

//그래프의 인접 리스트 표현
vector<vector<int>> adj;

//start에서 시작해 그래프를 너비 우선 탐색하고 각 정점의 방문 순서 반환
vector<int> bfs(int start){
	//각 정점의 방문여부 나타냄
    vector<bool> discovered(adj.size(), false);
    //방문할 정점 목록을 유지하는 큐
    queue<int> q;
    //정점의 방문 순서
    vector<int> order;
    
    dicovered[start] = true;
    q.push(start);
    
    while(!q.empty()){
        int here = q.front();
        q.pop();
        //here를 방문
        order.push_back(here);
        //모든 인접 정점 검사
        for(int i = 0; i < adj[here].size(); ++i){
            int there = adj[here][i];
            //방문한적 없는 정점의 경우 목록에 넣어줌
            if(!discovered[there]){
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

모든 정점을 한 번씩 방문하고 정점을 방문할 때마다 인접한 모든 간선을 검사한다.

따라서 인접 리스트로 구현한 경우 : O(|V| + |E|)

인접 행렬로 구현한 경우 O(|V|^2)의 시간 복잡도를 갖게 된다.

 

BFS와 최단거리

BFS의 경우엔 그래프 구조와 관련해 다양한 문제를 푸는데 사용되는 DFS와 달리 최단경로를 푸는 문제에 주로 사용된다.

위의 bfs코드를 약간 수정하면 두 정점을 연결하는 경로중 가장 거리가 짧은 경로를 찾는 코드를 만들 수 있다.(가중치 없는 그래프의 경우)

만약  bfs 수행 과정에서 간선(u,v)를 통해 정점 v를 발견하게 되었다면, 시작점에서 v까지의 최단거리는 시작점에서 u까지의 최단거리인 distance[u]에서 1을 더한 값이 되기 때문이다.

 

 

 

알고리즘 문제해결 전략(구종만)을 참고하여 작성하였습니다.