[기초] C++ 넓이 우선 탐색 (Breadth-First Search, BFS)

---

 

넓이 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로,

시작 정점에서부터 시작하여 인접한 정점들을 먼저 탐색한 후,

점차 멀리 있는 정점들을 탐색하는 방식입니다.

BFS는 주로 큐(Queue) 자료구조를 이용하여 구현되며,

그래프의 모든 정점을 방문하는 데 사용됩니다.

 

---

 

특징

 

• 시작 정점에서 가장 가까운 정점부터 탐색합니다.
  
  
• 최단 경로를 찾을 때 유용합니다.
  
  
• 큐(Queue) 자료구조를 사용하여 구현됩니다.
  
  

동작 원리

 

• 시작 정점을 큐에 삽입하고 방문 표시를 합니다.
  
  
• 큐에서 정점을 하나 꺼내어 해당 정점의 모든 인접 정점을 큐에 삽입하고,
  방문 표시를 합니다.
  
  
• 큐가 빌 때까지 2번 과정을 반복합니다.
  
  

#include <iostream>
#include <queue>

using namespace std;

const int MAX_VERTICES = 6;

void BFS(int start, int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    bool visited[MAX_VERTICES] = { false };
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";
        
        for (int i = 0; i < vertices; ++i) {
            if (adjMatrix[current][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    int vertices = MAX_VERTICES;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {0};
    
    // 그래프 초기화
    adjMatrix[0][1] = 1;
    adjMatrix[0][2] = 1;
    adjMatrix[1][0] = 1;
    adjMatrix[1][3] = 1;
    adjMatrix[1][4] = 1;
    adjMatrix[2][0] = 1;
    adjMatrix[2][4] = 1;
    adjMatrix[3][1] = 1;
    adjMatrix[3][5] = 1;
    adjMatrix[4][1] = 1;
    adjMatrix[4][2] = 1;
    adjMatrix[4][5] = 1;
    adjMatrix[5][3] = 1;
    adjMatrix[5][4] = 1;
    
    // BFS 시작
    cout << "BFS starting from vertex 0:" << endl;
    BFS(0, adjMatrix, vertices);
    
    return 0;
}

 

 

출력

 

BFS starting from vertex 0:
0 1 2 3 4 5

 

 

프로세스 설명

 

• 시작 정점 0을 큐에 넣고 방문 표시를 합니다.
  
  
• 큐에서 0을 꺼내고 인접한 정점 1과 2를 큐에 넣습니다.
  
  
• 큐에서 1을 꺼내고 인접한 정점 3과 4를 큐에 넣습니다.
  
  
• 큐에서 2를 꺼내지만 1과 4는 이미 방문했으므로 더 이상 진행하지 않습니다.
  
  
• 큐에서 3을 꺼내고 인접한 정점 5를 큐에 넣습니다.
  
  
• 큐에서 4를 꺼내지만 모든 인접한 정점이 이미 방문했으므로 더 이상 진행하지 않습니다.
  
  
• 큐에서 5를 꺼내지만 모든 인접한 정점이 이미 방문했으므로 더 이상 진행하지 않습니다.
  
  

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀