2-3. BFS - 너비 우선 탐색

1. BFS(Breadth First Search) ; 너비 우선 탐색

큐를 이용하여 시작 정점과 거리가 가까운 순으로 탐색.

(0 -> 1 -> 3 -> 2 or 4)

길찾기에 주로 사용됨.

시작 정점에서 가장 가까운 다음 정점들을 큐에 넣는 식으로 작동한다.

 

2. 여러 가지 방법

(1) 단일 리스트 방법

struct Vertex
{

};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);

그리고 discovered라는 이름의 변수를 이용하여 다음으로 진행할 정점을 저장한다.

void Bfs(int here)
{
	queue<int> q;
	q.push(here); // 시작 위치를 대입
	discovered[here] = true;

	while (q.empty() == false) // 방문할 정점이 없을 때까지 반복
	{
		here = q.front();
		q.pop(); // 다음으로 방문할 정점을 pop

		for (int there : adjacent[here])
		{
			if (discovered[there]) // 이미 발견했는지 체크
				continue;

			q.push(there); // 발견되지 않았다면 그 위치를 대입
			discovered[there] = true; // 발견 상태로 변경
		}
	}
}


int main()
{
	CreateGraph();

	discovered = vector<bool>(6, false);

}

(1) 큐에 시작 정점을 넣음 -> 시작 정점을 방문했음을 표시

(2) 대입된 정점을 꺼냄(pop)

(3) 인접한 정점을 탐색

(3-1) 발견되면 큐에 예약만 함.

(4) 발견된 정점을 큐에 넣고 해당 정점을 방문했음을 표시

(5) 그 정점을 꺼냄(pop)

(6) 인접한 정점을 탐색 ...

 

0을 시작 정점으로, 1 또는 3이 같은 깊이에 있다. 즉 큐에는 (1, 3)이 저장된 상태이다.

여기에서 front를 이용하여 1를 pop하게 되면 큐에는 3이 저장되어 있다.

이어서 다시 1을 시작 정점으로 탐색하여 2와 3이 있는 것을 알 수 있다.

여기서 이미 3은 큐에 들어있으므로, 2가 큐의 끝에 들어가게 된다.

이 때 정점3의 discovered가 true이므로 for문의 반복을 건너뛰게 된다.

따라서 here = 3인 상태에서 while문의 처음으로 돌아가게 된다.

 

이후에는 3이 pop되고 2가 시작 정점이 되면서 탐색이 다시 시작된다.

 

(1-2) 탐색되지 않은, 이어지지 않은 정점 찾기

void BfsAll()
{
	for (int i = 0; i < 6; i++)
	{
		if (discovered[i] == false)
			Bfs(i);
	}
}

 

(2) 인접 행렬 방법

 

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>
	{
		{ 0, 1, 0, 1, 0, 0},
		{ 1, 0, 1, 1, 0, 0},
		{ 0, 0, 0, 0, 0, 0},
		{ 0, 0, 0, 0, 1, 0},
		{ 0, 0, 0, 0, 0, 0},
		{ 0, 0, 0, 0, 1, 0},
	};

이중 반복문을 수정해준다.

		for (int there = 0; there < 6; there++)
		{
			if (adjacent[here][there] == 0;)
				continue;
			if (discovered[there]) // 이미 발견했는지 체크
				continue;

 

 

3. 길 찾기에서의 응용

누구에 의해서 발견 되었는지, 시작점에서 얼마나 떨어져 있는지 추적하면 길 찾기 알고리즘에 사용할 수 있다.

void Bfs(int here)
{
	// 누구에게 발견 되었는가?
	vector<int> parent(6, -1);
	// 시작점에서 얼마나 떨어져 있는가?
	vector<int> distance(6, -1);

이후에 이중 반복문을 수정해준다.

	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false) // 방문할 정점이 없을 때까지 반복
	{
		here = q.front();
		q.pop(); // 다음으로 방문할 정점을 pop

		for (int there : adjacent[here])
		{
			if (discovered[there]) // 이미 발견했는지 체크
				continue;

			q.push(there); // 발견되지 않았다면 그 위치를 대입
			discovered[there] = true; // 발견 상태로 변경

			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}

distance의 값이 -1로 나타나는 점은 길이 이어지지 않은 점, 0이면 자기 자신이다.

 

parent의 정보를 통해서 각 정점들이 어떻게 연결되어 있는지 알 수 있다.