너비 우선 탐색(Breadth First Search, BFS) 알고리즘

드디어 정렬 알고리즘이 끝나고 탐색 알고리즘이다. 이번 포스팅에서는 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘에 대해 알아보자.

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

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.
출처 : 위키백과

너비 우선 탐색은 맹목적인 탐색을 하고자 할 때 사용할 수 있는 탐색 기법이다. 최단 경로를 찾아준다는 점에서 최단길이를 보장해야 할 때 많이 사용된다.

특징

BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
BFS는 재귀적으로 동작하지 않는다.
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

다음의 그림을 보자

BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 또한 시작 노드를 방문했다고 방문 처리 를 해주도록 한다.

이제 BFS는 다음과 같은 알고리즘에 의해 동작한다.

큐에서 하나의 노드를 꺼낸다.
해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

위의 1번과 2번을 계속해서 반복하면 된다.

먼저 시작 노드 1을 큐에서 꺼냈다. 그리고 주변 노드인 2와 3이 모두 방문된 적이 없으므로 큐에 넣어준다. 결과는 위와 같다.

큐에서 2를 꺼낸 직후에는 그 인접한 노드 1, 3, 4, 5 중에서 1과 3은 이미 방문한 적이 있으므로 패스하고 4와 5를 큐에 삽입한다.

이후에 노드 3을 큐에서 꺼낸 뒤 인접한 노드인 6과 7을 삽입한다. 노드 1과 노드 2는 방문한 적이 있으므로 6과 7만 큐에 넣어주면 된다. 따라서 위와 같이 기본적으로 모든 노드가 방문처리가 되었다. 이제 남은 노드들을 큐에서 꺼내주기만 하면 된다.

차례대로 꺼내면 위와 같이 된다. 큐에서 꺼낸 순서를 보면 1, 2, 3, 4, 5, 6, 7이다. 아무렇게나 탐색하는 것이 아니라 이와 같이 1부터 ‘가까운’ 노드들 부터 탐색이 이루어진다는 점에서 너비 우선 탐색이라고 한다. 거리가 먼 노드인 4, 5, 6, 7은 가장 마지막에 탐색이 이루어지게 된다. C++코드로 구현하게 되면 다음과 같다.

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int const number = 7;
int c[8]; // 방문한 노드인지 기록
vector<int> a[8]; // 그래프를 표현할 벡터

void bfs(int start)
{
	queue<int> q;
	q.push(start); // 첫 번째 노드 큐에 삽입
	c[start] = true; // 시작 노드 방문 처리
	while (!q.empty())
	{
		int x = q.front(); // 맨 앞의 원소 저장
		q.pop(); // 맨 앞의 원소 삭제
		printf("%d ", x);
		for (int i = 0; i < a[x].size(); i++) // 각 벡터에 연결된 노드 수만큼 반복
		{
			int y = a[x][i]; // 현재 노드
			if (!c[y]) // 방문했었는지 확인
			{
				q.push(y); // 아직 방문하지 않은 노드들을 큐에 삽입
				c[y] = true; // 해당 원소 방문 처리
			}
		}

	}

}

int main(void)
{
	// 1과 2를 연결
	a[1].push_back(2);
	a[2].push_back(1);
	// 1과 3을 연결
	a[1].push_back(3);
	a[3].push_back(1);
	// 2와 3을 연결
	a[2].push_back(3);
	a[3].push_back(2);
	// 2와 4를 연결
	a[2].push_back(4);
	a[4].push_back(2);
	// 2와 5를 연결
	a[2].push_back(5);
	a[5].push_back(2);
	// 3과 6을 연결
	a[3].push_back(6);
	a[6].push_back(3);
	// 3과 7을 연결
	a[3].push_back(7);
	a[7].push_back(3);
	// 4와 5를 연결
	a[4].push_back(5);
	a[5].push_back(4);
	// 6과 7을 연결
	a[6].push_back(7);
	a[7].push_back(6);
	// BFS 수행
	bfs(1);
}

결과는 위와 같이 1 2 3 4 5 6 7의 순서로 탐색이 된 것을 확인할 수 있다.

참조
https://blog.naver.com/ndb796/221230944971
https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

Algorithm

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

특징

FEATURED TAGS

FRIENDS