너비 우선 탐색(Breath First Search)

개요

너비 우선 탐색은 말 그대로 탐색을 수행하는 알고리즘으로, 너비를 우선으로 한다. 이는 최단 경로 탐색에 많이 사용되며, 자료구조 중 큐(queue)를 사용한다는 특징이 있다.

너비 우선 탐색

너비 우선 탐색은 큐에 삽입된 첫 노드를 꺼내 연결된 노드 중 큐에 삽입되지 않은 노드를 모두 큐에 삽입한다. 이후 큐에 들어온 순서대로 해당되는 노드를 꺼내 모든 노드에 대해 위 방법을 반복한다. 이처럼 시작 노드를 기준으로 가장 가까운 노드부터 탐색해나가기에 너비 우선 탐색이라고 한다. 큐는 먼저 들어온 노드를 순서대로 처리하기에 위 방식을 사용하는 너비 우선 탐색에 어울리는 자료구조이다.

수행 과정

1. 시작 노드를 빈 큐에 삽입한다.
2. 큐에서 첫번째 노드인 시작 노드를 꺼내, 연결된 노드 중 큐에 삽입되지 않은 노드를 모두 큐에 삽입한다.
3. 큐에 삽입된 노드를 순서대로 꺼내 위 과정을 모든 노드에 대해 반복한다.

코드 구현

#include <iostream>
#include <queue>
#include <vector>

int main(){
    std::queue<int> q;
    int start_node{1};
    bool v[8];
    std::vector<int> a[8];
    
    a[1].emplace_back(2);
    a[2].emplace_back(1);
    a[1].emplace_back(3);
    a[3].emplace_back(1);
    a[2].emplace_back(3);
    a[3].emplace_back(2);
    a[2].emplace_back(4);
    a[4].emplace_back(2);
    a[2].emplace_back(5);
    a[5].emplace_back(2);
    a[3].emplace_back(6);
    a[6].emplace_back(3);
    a[3].emplace_back(7);
    a[7].emplace_back(3);
    a[4].emplace_back(5);
    a[5].emplace_back(4);
    a[6].emplace_back(7);
    a[7].emplace_back(6);

    q.push(start_node);
    v[start_node] = true;
    while (!q.empty()){
        int front = q.front();
        std::cout<<front<<' ';
        for (int i=0;i<a[front].size();i++){
            if (!v[a[front][i]]) {
                q.push(a[front][i]);
                v[a[front][i]] = true;
            }
        }
        q.pop();
    }

    return 0;
}
//1 2 3 4 5 6 7

Reference

https://m.blog.naver.com/ndb796/221230944971