너비 우선 탐색(BFS, Breadth First Search)

너비 우선 탐색(BFS) 이란?

너비 우선 탐색 (BFS, Breadth First Search)은 DFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다.

BFS 알고리즘은 현재의 위치에서 방문할 수 있는 모든 정점을 방문한 뒤 다음 단계로 넘어가는 방식입니다.

일반적으로 BFS 알고리즘을 구현할 때 큐를 이용합니다.

너비 우선 탐색(BFS) 방법

아래는 BFS를 설명하기 위해 작성한 간단한 그래프입니다.

원안의 1,2,3.. 등을 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다.

우선 시작점을 1로 정하고 BFS 알고리즘을 바탕으로 탐색을 해보겠습니다.

 

시작점인 1번 정점을 큐에 넣고 해당 위치에 방문을 했다고 표시합니다.

 

 

1번 정점과 연결된 2번, 3번 정점을 큐에 넣고 해당 위치에 방문 했다고 표시합니다.

위의 그림에는 표시가 되지 않았지만 현재위치는 큐에서 제거를 하게 됩니다.

 

현재 위치인 2번 정점은 방문하지 않은 근접 노드 4번, 5번 정점을 큐에 넣고 해당 위치를 방문 했다고 표시합니다.

이후 2번 정점을 큐에서 제거합니다.

 

3번 정점에서 방문하지 않은 근접 노드 6번을 큐에 넣고 해당 위치를 방문 했다고 표시합니다.

이후 3번 정점을 큐에서 제거합니다.

 

4번 정점에서 방문하지 않은 근접 노드 7번을 큐에 넣고 해당 위치를 방문 했다고 표시합니다.

이후 4번 정점을 큐에서 제거합니다.

 

5번 정점에서 방문하지 않은 근접노드가 없기 때문에 큐에 아무것도 넣지 않습니다.

이후 5번 정점을 큐에서 제거합니다.

 

6번 정점에서 방문하지 않은 근접노드가 없기 때문에 큐에 아무것도 넣지 않습니다.

이후 6번 정점을 큐에서 제거합니다.

 

 

7번 정점에서 방문하지 않은 근접노드가 없기 때문에 큐에 아무것도 넣지 않습니다.

이후 7번 정점을 큐에서 제거를 하며, 큐에 아무값도 없으면 탐색을 종료합니다.

 

너비 우선 탐색(BFS) 예제

백준 1260번: DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int n, m; // 정점, 간선
int v; // 탐색을 시작할 정점의 번호
int s, e; //시작점, 끝점
int matrix[1002][1002];
int visit[1002];
queue<int> Q;
int check[1002];

void dfs(int x)
{
	visit[x] = 1;
	printf("%d ", x);
	for (int i = 1; i <= n; i++)
	{
		if (matrix[x][i] == 1 && visit[i] == 0)
			dfs(i);
	}
}

void bfs(int x)
{
	check[x] = 1;
	Q.push(x);
	while (!Q.empty())
	{
		int t = Q.front();
		Q.pop();
		printf("%d ", t);
		for (int i = 1; i <= n; i++)
		{
			if (matrix[t][i] == 1 && check[i] == 0)
			{
				check[i] = 1;
				Q.push(i);
			}
		}
	}
}


int main(int argc, char *argv[])
{
	scanf("%d %d %d", &n, &m, &v);
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &s, &e);
		matrix[s][e] = matrix[e][s] = 1;
	}
	dfs(v);
	printf("\n");
	bfs(v);
	printf("\n");

	return 0;
}