BFS란?
BFS는 그래프 순회 알고리즘인 Breadth-First Search의 약자입니다. 레벨별로 그래프 또는 트리의 모든 정점을 탐색합니다. 다음 레벨로 이동하기 전에 동일한 레벨의 모든 정점을 방문합니다.
BFS 과정
- 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다.
- 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
큐에서 꺼내 처리 중인 노드는 파란색으로, 방문 처리한 노드는 회색으로 표시하겠습니다.
(1) 시작 노드인 노드 1을 큐에 삽입하고 방문 처리합니다.
(2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 방문 처리합니다.
(3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 방문 처리합니다.
(4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 방문 처리합니다.
(5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 방문 처리합니다.
(6) 그래프 내 노드에서 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼냅니다.
결과적으로 노드의 탐색 순서, 즉 큐에 삽입한 순서는 다음과 같습니다.
1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7
BFS 구현(백준 24444번)
문제
입력
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.
출력
첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
vector<vector<int>> graph(M + 1);
for (int i = 1; i <= M; i++)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= N; i++)
sort(graph[i].begin(), graph[i].end());
vector<int> visited(N + 1, 0);
BFS(visited, graph, R);
for (int i = 1; i <= N; i++)
{
cout << visited[i] << "\n";
}
return 0;
}"1 2"가 입력으로 주어졌을 때 graph[1]에 원소로 2를 넣고 연결 그래프이므로 graph[2]에도 원소로 1을 넣는다.
인접 정점은 오름차순으로 방문해야 하므로 오름차순으로 정렬해준다.
int cnt = 0;
void BFS(vector<int>& V, vector<vector<int>>& E, int R)
{
queue<int> q;
q.push(R);
cnt++;
V[R] = cnt;
while (!q.empty())
{
int element = q.front();
q.pop();
for (int i = 0; i < E[element].size(); i++)
{
int temp = E[element][i];
if (!V[temp])
{
cnt++;
V[temp] = cnt;
q.push(temp);
}
}
}
}queue q에 시작 정점 R을 넣습니다. 그리고 cnt를 1 증가해주고 방문 여부와 방문 순서를 표시해주는 배열 V의 R번째 원소에 cnt를 넣습니다. 큐가 비어 있지 않다면 시작 정점 R에 인접한 원소도 똑같이 큐가 빌 때까지 진행해 줍니다.
References
