너비 우선 탐색 (BFS)

너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 않은 정점을 찾아 순차적으로 방문해 나아간다. 

 

더이상 방문할 수 없을때 까지 반복하며, 인접한 간선을 우선적으로 검사하기 위하여 Queue를 사용한다. 어떻게 진행되는지를 그림을 통해 살펴보자.

 

1을 방문하면서 인접한 정점인 2, 3, 그리고 7을 큐에 넣어준다. 그리고 큐에 들어간 순서대로 방문하면서 큐가 빌때까지 반복 수행해준다. 이 작업을 모든 정점이 방문되었을때까지 반복해주면 된다.

---

구현

위 그래프 정보를 바탕으로 깊이 탐색을 구현해보자. 

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

#define VISITED 1
#define UNVISITED 0
#define CONNECTED 1

using namespace std;

// 인접행렬로 간선을 표현한것
vector<vector<int>> edge =
{
	{0, 1, 1, 0, 0, 0, 0},
	{1, 0, 0, 1, 1, 0, 0},
	{1, 0, 0, 0, 0, 0, 1},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 1, 0, 0, 0, 1, 0},
	{0, 0, 0, 1, 1, 0, 1},
	{0, 0, 1, 0, 0, 1, 0}
};

vector<int> vertices;

// 너비 우선 탐색
void BFS(int index)
{
	// 정점에 대해 방문처리를 한다.
	vertices[index] = VISITED;

	// 정점 정보를 큐에 넣는다.
	queue<int> q;
	q.push(index);
	cout << index + 1 << " ";

	// 큐가 빌때까지 반복한다.
	while (false == q.empty())
	{
		// 큐에 들어간 정점 정보 순서대로 방문이 가능한지 반복한다.
		int sub_index = q.front();
		q.pop();

		for (size_t i = 0; i < edge.size(); ++i)
		{
			// 연결되어 있고 방문한 적이 없는 정점이 있는 경우
			if (CONNECTED == edge[i][sub_index] &&
				UNVISITED == vertices[i])
			{
				cout << i + 1 << " ";
				q.push(i);

				vertices[i] = VISITED;
			}
		}
	}
}

int main()
{
	vertices = vector<int>(edge.size(), UNVISITED);
	
	// 모든 정점을 방문할 때까지 너비 우선탐색을 반복한다.
	for (size_t i = 0; i < edge.size(); ++i)
	{
		if (UNVISITED == vertices[i])
			BFS(i);
	}

	cout << endl;
}

 

출력값

1 2 3 4 5 7 6