queue를 이용한 BFS 구현

BFS (Breadth-First-Search) 너비 우선 탐색?

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

해석해보면,

• 트리 / 그래프 자료구조를 순회하거나 탐색할 때 사용한다.
• 루트 노드에서 시작하여 현재 깊이의 모든 노드 탐색한 후, 다음 깊이 레벨의 노드를 모두 탐색하는 것을 반복한다.

---

BFS의 특징 / 사용하는 경우

• 탐색 속도 자체는 DFS보다 빠르다.
• 모든 노드를 방문해야 하는 경우 사용할 수 있다.
• 최단 거리를 구해야 할 경우 사용한다. 루트 노드에서 가까운 곳부터 탐색하기 때문에 먼저 발견한 경로가 최단 거리이다.
• 너무 깊은 경로로 빠지지 않을 수 있다.

활용 문제

---

실습 코드

루트 노드와 연결된 모든 노드를 queue에 push한다. 현재 깊이의 모든 노드를 탐색한 후에, queue에 push 했던 원소를 하나씩 pop해서 그 노드와 연결된 자식 노드를 또 다시 queue에 push 하는 과정을 반복한다. 목표 노드에 도착하거나, 모든 노드를 방문하면 종료한다. 그리고 한번 방문한 노드는 다시 방문하지 않도록 구현한다.

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

using namespace std;
//show all elememts in the queue
void showAll(queue<int> q) {
    while(!q.empty()){
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

int main(void) {
    queue<int> q;
    bool visited[10] = { 0, };
    vector<int> v[10] = { {}, {2, 3}, {1, 3, 4, 5}, \
    {1, 2, 6, 7}, { 2, 8 }, { 2, 9 }, { 3 }, { 3 }, { 4 }, { 5 } };

    // check first node as a visited node
    visited[1] = true;

    //push first node's connected nodes
    for (auto i = v[1].begin(); i != v[1].end(); i++) {
        q.push(*i);
        visited[*i] = true;
    }
    cout << "show all elements : ";
    showAll(q);

    while (!q.empty()) {
        // print the front element(cur_node) and pop it.
        int cur_node = q.front();
        cout << "cur_node : " << q.front() << endl;
        q.pop();

        // push cur_node's connected nodes
        for (auto i = v[cur_node].begin(); i != v[cur_node].end(); i++) {
            if (visited[*i] == false) {
                q.push(*i);
                visited[*i] = true;
            }
        }
        cout << "show all elements: ";
        showAll(q);
    }

    return 0;
}

[실행 결과]

show all elements : 2 3
cur_node : 2
show all elements: 3 4 5
cur_node : 3
show all elements: 4 5 6 7
cur_node : 4
show all elements: 5 6 7 8
cur_node : 5
show all elements: 6 7 8 9
cur_node : 6
show all elements: 7 8 9
cur_node : 7
show all elements: 8 9
cur_node : 8
show all elements: 9
cur_node : 9
show all elements:

[comment]

while 문으로 queue가 빌 때까지 반복하는데, 처음에 queue가 비어있으면 안되기 때문에 root node에 대해서는 while문보다 먼저 push/pop을 구현했다. 그래프의 연결 노드에 대한 정보는 vector를 활용해서 저장하고, 방문했는지 여부는 bool array를 활용했다.

---

reference

• https://en.wikipedia.org/wiki/Breadth-first_search