[알고리즘] 너비 우선 탐색(Breadth First Search)

 

 

 

 

 

알고리즘 개요 및 소개

BFS ANimation

너비 우선 탐색(Breadth First Search, BFS)은 *맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않는 모든 정점들에 대해서도 너비 우선 탐색을 적용한다. 큐를 사용해야 레벨 순서대로 접근이 가능하다.

 

*맹목적 탐색: 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법

시간 복잡도	인접 리스트: O(|V|+|E|) 인접 행렬: O(|V|^2) V: 정점의 수 E: 간선의 수
장점	출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
단점	- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. - 해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다. - 무한 그래프의 경우에는 해를 찾지도 끝내지도 못한다.

 

탐색 과정

 

너비 우선 탐색의 알고리즘은 다음과 같다.

1. Queue에 가장 앞에 있는 노드를 pop
2. POP 한 노드에 방문하지 않은 인접 노드를 모두 Queue에 Push
3. Queue가 Empty 상태가 아니라면 위 순서를 반복

초기상태

1번 노드를 맨 처음 방문한다는 가정하에 시작을 하면 Queue에 1을 Push 한다.

1번 노드의 인접노드를 방문

 

Queue에 가장 앞에 있는 1번 노드를 pop 한 후 1번 노드의 인접 노드 중 방문을 하지 않는 노드들(2번, 3번)을 모두 Queue에 Push 한다.

2번 노드의 인접노드를 방문

 

Queue에 가장 앞에 있는 2번 노드를 pop 한 후 2번 노드의 인접 노드 중 방문을 하지 않는 노드들(4번, 5번)을 모두 Queue에 Push 한다.

 

3번 노드의 인접노드를 방문

Queue에 가장 앞에 있는 3번 노드를 pop 한 후 3번 노드의 인접 노드 중 방문을 하지 않는 노드들(6번, 7번)을 모두 Queue에 Push 한다.

 

이후 더 이상 방문하지 않은 인접 노드가 없기 때문에 탐색은 종료가 된다.

 

소스코드

#include<iostream>
#include<queue>
#include<vector>
 
constexpr int MAX = 8;
 
class Graph {
private:
    std::vector<int> node_[MAX];
    bool is_visited_[MAX];
public:
    Graph() {
        for (int i = 0; i < MAX; ++i)
            is_visited_[i] = false;
    };
    void InitNode() {
        //1번 노드에 2,3을 넣음
        node_[1].emplace_back(2);
        node_[1].emplace_back(3);
        //2번 노드에 1,4,5을 넣음
        node_[2].emplace_back(1);
        node_[2].emplace_back(4);
        node_[2].emplace_back(5);
        //3번 노드에 1,6,7을 넣음
        node_[3].emplace_back(1);
        node_[3].emplace_back(6);
        node_[3].emplace_back(7);
        //4번 노드에 2,5을 넣음
        node_[4].emplace_back(2);
        node_[4].emplace_back(5);
        //5번 노드에 2,4를 넣음
        node_[5].emplace_back(2);
        node_[5].emplace_back(4);
        //6번 노드에 3,7을 넣음
        node_[6].emplace_back(3);
        node_[6].emplace_back(7);
        //7번 노드에 3,6을 넣음
        node_[7].emplace_back(3);
        node_[7].emplace_back(6);
    }
    void BFS(int started) {
        std::queue<int> q;
        q.push(started);
        is_visited_[started] = true;
 
        while (q.empty() == false) {
        
            int curr = q.front();
            q.pop();
            std::cout << curr << " ";
            for (int i = 0; i<node_[curr].size(); ++i) {
                int node = node_[curr][i];
 
                if (is_visited_[node] == false) {
                    q.push(node_[curr][i]);
                    is_visited_[node] = true;
                }
            }
        }
 
    }
    void DFS(int started) {
 
 
    
    }
};
 
 
 
 
 
int main() {
    Graph g;
    g.InitNode();
    g.BFS(2);
}

후기

결과

 

탐색의 방법 중 하나인 너비 우선 탐색(BFS)을 구현해 보았다. 알고리즘 시간에 다른 수업의 과제를 하다 보니 탐색 부분이 많이 약해서 걱정이었는데 트리나 그래프 등을 제대로 공부할 수 있는 시간이 된 거 같다. 아직 배워야 할 알고리즘도 많고 응용문제도 풀어봐야 하지만 차근차근할 예정이다.

 

깊이 우선 탐색(Depth First Search)

그래프(Graph)

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/너비_우선_탐색

그림: 본인