23.06.12 Breadth First Search

Breadth First Search (BFS)

넓이 우선 탐색 

그래프 또는 트리 데이터 구조를 순회하거나 검색하는 알고리즘 

 

BFS 의 단계 

1. initialization

2. 첫번째 노드를 방문하고 해당 노드의 인접 노드 모두 탐색

3. 모든 노드를 방문할 때까지 해당 작업 반복

 

BFS 를 구현하기 위해서는 큐 자료 구조를 이용할 수 있다.

 

BFS vs DFS 

왜 BFS 를 구현할 때는 스택을 사용하지 않고 큐를 사용할까?

해당 노드에 대한 인접 노드 정보를 저장할 때 push 하는데

자료 구조의 특성 상, 스택은 가장 마지막에 넣은 노드를 꺼내게 되고 큐는 가장 처음에 넣은 노드를 꺼내게 된다. 

이때, 넓이 우선 탐색을 하려면 같은 레벨의 노드를 우선적으로 탐색해야 하므로

다음 레벨의 인접 노드보다 먼저 들어간 노드를 꺼내기 위해서 큐를 사용하는 것이 바람직하다. 

 

코드를 살펴보면 

#include <iostream>
#include <queue>
using namespace std;

bool visited[9];
vector<int> graph[9];

 

queue 에 시작 노드 입력해주고 큐를 비울 때까지 큐의 헤드 요소를 꺼내서 방문 처리를 해준다. 

void bfs(int x) {
    queue<int> nodes;
    nodes.push(x);
    visited[x] = true;

    while(!nodes.empty()) {
        int head = nodes.front();
        nodes.pop();
        cout << head << ' ';
        for(int i = 0; i < graph[head].size(); i++) {
            int y = graph[head][i];
            if(!visited[y]) {
                nodes.push(y);
                visited[y] = true;
            }
        }
    }
}

 

 

main 함수에서 DFS 와 마찬가지로 인접 노드 설정과 bfs 함수를 실행해준다. 

int main() {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);
    
    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);
    
    bfs(1);
}

실행 결과는 다음과 같다. 

## BFS
1 2 3 8 7 4 5 6

## DFS
1 2 7 6 8 3 4 5

DFS 결과와 비교하면 같은 레벨의 노드부터 모두 탐색한 후에

다음 레벨의 노드를 탐색하는 것을 확인할 수 있었다~!~!