너비 우선 탐색

이 문서는 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. 추천 문제



분류 알고리즘