[C++로 배우는 알고리즘과 자료구조] Day 24: 너비 우선 탐색 (BFS)

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

너비 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 인접한 정점들을 모두 탐색한 후, 탐색이 끝난 정점의 인접 정점을 탐색하는 방식입니다. BFS는 큐 자료구조를 사용하여 구현할 수 있습니다.

BFS의 주요 특징:

• 시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.
• 공간 복잡도: (O(V)), 큐와 방문 여부를 저장하는 배열의 크기입니다.

BFS 구현

그래프 구현 (인접 리스트 사용)

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

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w); // 간선 추가
    void BFS(int s); // BFS 호출

private:
    int vertices; // 정점의 수
    std::vector<std::list<int>> adjList; // 인접 리스트
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가 함수 정의
void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // 정점 v에 정점 w를 추가
}

// BFS 호출 함수 정의
void Graph::BFS(int s) {
    std::vector<bool> visited(vertices, false); // 모든 노드를 방문하지 않은 상태로 초기화
    std::queue<int> queue; // 탐색할 정점을 저장할 큐

    // 시작 정점을 방문한 것으로 표시하고 큐에 추가
    visited[s] = true;
    queue.push(s);

    while (!queue.empty()) {
        // 큐에서 정점을 하나 꺼내서 출력
        s = queue.front();
        std::cout << s << " ";
        queue.pop();

        // 현재 정점과 인접한 모든 정점을 방문
        for (auto i = adjList[s].begin(); i != adjList[s].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push(*i);
            }
        }
    }
}

// 메인 함수
int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "정점 2에서 시작하는 너비 우선 탐색: ";
    g.BFS(2);

    return 0;
}

 

설명

1. 그래프 클래스:
   • vertices: 그래프의 정점 수.
   • adjList: 각 정점의 인접 리스트를 저장하는 벡터.
2. addEdge 함수:
   • 정점 v에서 정점 w로의 간선을 그래프에 추가합니다.
3. BFS 함수:
   • 주어진 시작 정점에서 BFS를 수행합니다.
   • 방문 여부를 추적하기 위해 visited 벡터를 사용하고, 탐색할 정점을 저장하기 위해 큐를 사용합니다.
   • 시작 정점을 방문한 것으로 표시하고 큐에 추가한 후, 큐가 빌 때까지 반복합니다.
   • 큐에서 정점을 하나 꺼내서 출력하고, 현재 정점과 인접한 모든 정점을 방문합니다.

BFS의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 탐색 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 25: 다익스트라 알고리즘"에 대해 학습하겠습니다.