[c++] 너비 우선 탐색 (BFS)

08 Dec 2023

너비 우선 탐색(Breadth-First Search, BFS)은 그래프를 탐색하는 데 사용되는 알고리즘 중 하나입니다. 이 알고리즘은 특정한 정점에서 시작하여 인접한 정점들을 먼저 탐색하는 방식으로 동작합니다. BFS는 큐(Queue)를 사용하여 구현되며, 한 번 방문한 정점은 다시 방문하지 않도록 처리됩니다.

BFS 알고리즘의 구현

아래는 C++에서 BFS 알고리즘을 구현하는 간단한 예제 코드입니다.

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

using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    int n = 6; // 그래프의 정점 수
    vector<vector<int>> graph(n+1); // 1부터 인덱스 시작

    // 그래프의 간선 추가
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(5);
    graph[4].push_back(6);
    graph[5].push_back(6);

    cout << "BFS 탐색 결과: ";
    bfs(graph, 1); // 정점 1에서 시작

    return 0;
}

이 예제 코드는 큐를 사용하여 BFS를 구현하고, 방문한 정점을 표시하기 위해 visited 배열을 사용합니다.

결론

BFS 알고리즘은 그래프를 탐색하는 간단하면서도 효율적인 방법을 제공합니다. BFS를 이용하면 최단 경로 문제나 네트워크 트aversal과 같은 다양한 문제를 해결할 수 있습니다.

더 많은 정보를 원한다면 링크를 참고해보세요.