[알고리즘] BFS(Breadth First Search)이란?

1. BFS 알고리즘 개념

2. BFS 알고리즘 동작 방식

3. BFS 알고리즘 구현 코드

BFS(Breadth First Search) 알고리즘이란?

BFS 알고리즘은 너비 우선 탐색 알고리즘이다. 그래프 탐색 시, 가까운 인접 노드를 모두 방문한 후, 그 다음 가까운 인접 노드를 방문하는 방식이다. 일반적으로, 자료구조 큐(Queue)를 이용하여 문제를 해결한다. 

동작 방식

아래와 같은 방향이 없는 그래프에서 같은 레벨인 경우, 작은 번호 기준으로 방문한다고 가정한다.

• 노드 1번부터 시작해서 노드 1번을 큐에 넣고 방문 처리한다.
• 큐에서 노드 1번을 꺼내 인접한 노드들(2, 3, 8)을 확인하고, 방문하지 않은 노드들을 큐에 넣고 방문 처리한다.
• 큐에서 2번 노드를 꺼내어 인접한 노드들인 8번과 6번을 확인하고, 방문하지 않은 6번 노드를 큐에 넣고 방문 처리한다. 
• 큐에서 3번 노드를 꺼내 인접한 4번과 5번 노드를 큐에 넣고, 둘 다 방문 처리한다.
• 큐에서 8번 노드를 꺼내 방문하지 않은 인접한 노드가 없기 때문에 다음 노드를 처리한다.
• ...
• 큐가 empty일 때까지 위와 같은 동일한 과정을 반복한다. 

이런식으로, 큐에서 다음 차례 노드의 인접한 노드 중 아직 방문하지 않은 노드를 큐에 넣고 방문하는 식으로 탐색한다.

 

또 다른 동작 과정 예시는 다음과 같다. 

 

C++ BFS 구현 코드

#include <bits/stdc++.h>

using namespace std;

// 방문 여부를 체크할 배열
bool visited[9];
// 그래프의 인접 리스트 표현
vector<int> graph[9];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 현재 노드와 연결된 다른 노드를 확인
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 그래프를 초기화 (간선 연결)
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(1);
    graph[3].push_back(6);
    graph[3].push_back(7);
    graph[4].push_back(2);
    graph[5].push_back(2);
    graph[6].push_back(3);
    graph[7].push_back(3);
    graph[4].push_back(8);
    graph[8].push_back(4);

    // BFS 실행
    bfs(1);

    return 0;
}

 

출력 결과는 다음과 같다.

 

References

(이코테 2021 강의 몰아보기) 3. DFS & BFS