너비 우선 탐색

이 문서는 BFS(으)로 검색해도 들어올 수 있습니다.
[접기]

목차

  • 1. 너비 우선 탐색


BFS는 2가지 알고리즘의 약자로 각각 너비 우선 탐색(Breadth-First Search)과 최선 우선 탐색(Best-First Search)이다.

1. 너비 우선 탐색


1.1. 알고리즘



1.2. 소스 코드


1부터 n까지의 정점으로 구성된 그래프를 BFS로 탐색하는 프로그램에 대한 코드이다.

#include
#include
#include
using namespace std;

vector ad[1010];
bool vis[1010];

void bfs(int v) {
queue q;
q.push(v);
vis[v] = true;
while (!q.empty()) {
int p = q.front(); q.pop();
printf("%d ", p);
for (int next : ad[p]) {
if (vis[next]) continue;
q.push(next);
vis[next] = true;
}
}
}
메인에서 다음과 같이 사용한다.

for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
bfs(i);
}

1.3. 추천 문제



분류 알고리즘