BFS (너비 우선 탐색) C++

BFS (너비 우선 탐색)

BFS는 탐색을 할 때 너비를 우선으로 수행하는 그래프 탐색 알고리즘이다.
너비 우선 탐색은 최단 경로를 찾아야 할 때 많이 사용한다.
재귀 함수로 구현하지 않고 큐(Queue)로 주로 구현한다.

 

BFS를 그래프를 저장 할 때는 인접 행렬과 인접 리스트로 구현하는 방법이 있는데 인접 행렬은 시간 복잡도가 O(V^2) (V는 정점의 수), 인접 리스트는 O(V + E) (V는 정점, E는 간선) 이라 인접 리스트가 더 빠르기 때문에 주로 인접 리스트로 저장한다.

C++ BFS 구현

bool visited[101] = {};
void bfs(vector<int> graph[], 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;
            }
        }
    }
}