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

Goal

너비 우선 탐색(BFS, Breadth-First Search)의 개념
너비 우선 탐색(BFS, Breadth-First Search)의 특징
너비 우선 탐색(BFS, Breadth-First Search)의 구현

 

그래프 탐색이란?

 

• 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 

• 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다.

 

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

 

• 너비 우선 탐색은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 
• 쉽게 말해 정점과 정점 사이의 거리를 d라고 할 때, 우선 시작 정점과의 거리가 1인 정점들을 모두 탐색한 후 그다음 거리가 2인 정점들을 모두 탐색하는 방식이다.
• 너비 우선 탐색을 하기 위해서는 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요하다.
• DFS와는 다르게 BFS는 최단경로 또는 임의의 경로를 찾을 때 사용합니다. 
• 하지만, DFS처럼 컴포넌트의 크기, 개수를 셀 수 있습니다.

 

 

 

너비 우선 탐색 특징

 

1. 재귀적으로 동작하지 않는다.
2. 정점의 방문 여부를 반드시 검사해야 한다.
3. 선입선출(FIFO)를 원칙으로 하는 자료구조인 큐(Queue)를 사용한다.

 

 

너비 우선 탐색의 과정

 

 

(a) 가장 먼저 시작 정점을 큐에 넣습니다.

(b) 가장 처음에 넣은 0을 큐에서 pop 한 후 해당 정점과 인접한 정점을 모두 큐에 넣습니다.

-> 이때 값을 오름차순으로 넣고 싶다면 정렬을 먼저 실행해 줍니다.

(f) 인접한 정점을 모두 넣었다면 가장 처음 넣은 정점을 pop 한 후 해당 정점에 대해서 (b) ~ (e) 의 과정을 pop 할 데이터가 없어질 때까지 반복합니다.

 

너비 우선 탐색의 구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
class Graph{
public:
    int N; // 정점의 개수
    vector<vector<int>> adj; // 인접 리스트
 
    // 생성자
    Graph(): N(0){} //인수 입력을 안한경우
    Graph(int n): N(n){ adj.resize(N); }
 
    // 간선 추가 함수
    void addEdge(int u, int v){ 
        adj[u].push_back(v);
        adj[v].push_back(u);
    } 
 	// 기본적으로 무방향 그래프
    
    // 모든 리스트의 인접한 정점 번호 정렬
    void sortList(){
        for(int i=0; i<N; i++)
            sort(adj[i].begin(), adj[i].end());
    }
 	//정렬은 안해도 문제 없지만, 안 하는 경우 
    //탐색 순서가 항상 바뀔 수 있다.
    
    // 너비 우선 탐색
    void bfs(){
        vector<bool> visited(N, false); // 방문 여부를 저장하는 배열
        queue<int> Q;
        Q.push(0); //시작 정점 PUSH
        visited[0] = true; //방문 표시
        
        // 탐색 시작
        while(!Q.empty()){
            int curr = Q.front();
            Q.pop();
            cout << "node " << curr << " visited" << endl;
            for(int next: adj[curr]){
                if(!visited[next]){
                    visited[next] = true;
                    Q.push(next);
                }
            }
        }
    }
};
 
int main(){
    Graph G(9);
    G.addEdge(0, 1);
    G.addEdge(0, 2);
    G.addEdge(1, 3);
    G.addEdge(1, 5);
    G.addEdge(3, 4);
    G.addEdge(4, 5);
    G.addEdge(2, 6);
    G.addEdge(2, 8);
    G.addEdge(6, 7);
    G.addEdge(6, 8);
    G.sortList();
    G.bfs();
}

 

 [출처] 너비 우선 탐색(Breadth-First Search) 작성자 라이  https://kks227.blog.me/220785747864