설명

• BFS : Breadth-First Search
• 그래프나 트리에서 너비를 우선으로 탐색하는 알고리즘
• 그래프나 트리에서 시작 정점으로부터 가까운 정점부터 탐색하는 알고리즘
• queue를 통해 구현
• 각 정점을 방문하면서 그 정점의 모든 인접 정점을 큐에 삽입 → 큐가 빌 때까지 반복
• 최단 경로 문제, 모든 정점 방문하는 문제

예제

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

using namespace std;

void bfs(int start, vector<vector<int>& graph>) {
	vector<bool> visited(graph.size(), false);
    queue<int> que;
    que.push(start);
    visited[start] = true;
    
    while(!que.empty()) {
    	int node = que.front();
        que.pop();
        cout << node << " ";
        
        for(int neighbor : graph[node]) {
        	if(!visited[neighbor]) {
            	que.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
	int n = 6;
    vector<vector<int>> graph(n);
    graph = {{1,2}, {0,3,4}, {0,4}, {1}, {1,2,5}, {4}};
    
    bfs(0, graph);
    
    return 0;
}

결과

• 0 1 2 3 4 5

탐색 순서 설명

1. 0에서 시작
2. 0의 자식 1과 2를 큐에 넣음
3. 1을 방문하고, 1의 자식 3과 4를 큐에 넣음
4. 2를 방문하고, 2의 자식 4는 이미 방문되었으므로 추가하지 않음
5. 3을 방문하고, 3의 자식이 없으므로 넘어감
6. 4를 방문하고, 4의 자식 5를 큐에 넣음
7. 5를 방문하고, 5의 자식이 없으므로 탐색 종료

예제 그래프