너비 우선 탐색
이 문서는
BFS(으)로 검색해도 들어올 수 있습니다.
BFS는 2가지 알고리즘의 약자로 각각 너비 우선 탐색(Breadth-First Search)과 최선 우선 탐색(Best-First Search)이다.
1. 너비 우선 탐색
1.1. 알고리즘
- 큐를 준비한다.
- 어떠한 노드에서 시작한다.
- 인접한 노드들 중 아직 방문하지 않은 노드들을 큐에 넣는다.
- 큐에 저장된 노드들을 방문하고, 각각에 대해 인접한 노드들 중 아직 방문하지 않은 노드들을 큐에 넣는다.
- 큐가 완전히 빌 때까지 반복한다.
1.2. 소스 코드
1부터 n까지의 정점으로 구성된 그래프를 BFS로 탐색하는 프로그램에 대한 코드이다.
- C++
#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. 추천 문제
분류
알고리즘

- ISU 위키의 모든 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 제외)
- 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.