[Algorithm] BFS

이번글은 BFS에 대한 글입니다!

그래프와 BFS란?

그래프란 정점과 간선으로 이루어진 자료구조입니다.

실생활에서도 많이 쓰이기 때문에 그래프는 중요한 개념입니다.

종류로는 "무방향 그래프", "완전 그래프", "가중치 그래프" 등등 종류가 많습니다.

그래서 탐색하는 방법이 그래프 구현에 따라 달라집니다. 그럼에도 불구하고 그래프의 모든 정점을 탐색하는 그래프가 대표적으로 아래 두가지가 있습니다.

- DFS : Depth First Search

- BFS : Breadth First Search 

이중에서도 BFS를 구현하는 방법을 알려드리도록 하겠습니다.

 

일단 그래프를 탐색하려면 그래프가 있어야겠죠?

그래프를 구현하는 대표적인 방법두가지를 알려드리도록 하겠습니다.

- 인접 리스트를 통한 그래프 구현 => 정방 행렬을 사용

- 연결 리스트를 통한 그래프 구현 => 연결 리스트를 사용

 

BFS는 가장 가까운 녀석부터 탐색을 하는 것이라고 보면되겠습니다.

출발점이 A라고 할때 A로 부터 가장 가까운녀석부터 방문하고 DFS는 각개격파 식으로 하나하나 타고 들어가며 방문하는 방식이라고 알아주시면 되겠습니다.

구현

이렇게 있는데 저는 연결 리스트를 사용해서 구현을 하도록 하겠습니다.

참고로 인접 리스트를 통해 구현하는것은 

int arr[10][10] = {};

위와 같은 정방행렬을 사용하는 것이고

인접리스트는 말 그대로 진짜 리스트를 사용해도 되고 vector를 통해서 구현하셔도 됩니다.

저는 vector를 통해서 구현하도록 하겠습니다.

또한 BFS를 구현하면서 필요한 자료구조가 있습니다! 바로 queue입니다.

queue의 특징은 선입선출이죠? 가장 A에서 출발해서 연결된 노드들을 큐에다가 담고 

트리(그래프)를 한계단씩 내려가며 큐를 비우며 탐색을 하는 것입니다.

 

바로 코드를 보며 이해를 하도록 해보겠습니다!

#include <iostream>
#include "BFS.h"
#include <vector>
#include <queue>
using namespace std;

const int numberOfVertex = 7;

enum { A, B, C, D, E, F };
std::vector<int> visit;


int main()
{
	std::vector<vector<int>> vec = std::vector<vector<int>>(numberOfVertex, std::vector<int>(numberOfVertex, -1));

	visit = std::vector<int>(numberOfVertex, -1);

	vec[A][B] = B;
	vec[B][A] = A;

	vec[A][C] = C;
	vec[C][A] = A;

	vec[A][D] = D;
	vec[D][A] = A;
	
	vec[C][E] = E;
	vec[E][C] = C;

	vec[C][F] = F;
	vec[F][C] = C;

	vec[D][F] = F;
	vec[F][D] = D;

	std::queue<int> q;
	int start = A;
	q.push(start);
	visit[start] = 1;
	
	while (!q.empty())
	{
		int next = q.front();
		q.pop();
		cout << char(next + 65) << " 방문";
		cout << endl;

		for (int i = 0; i < numberOfVertex; ++i)
		{
			if (vec[next][i] != -1 && visit[i] != 1)
			{
				q.push(i);
				visit[i] = 1;
			}
		}
	}
	
	return 0;
}

핵심은 방문한 곳을 다시 방문하지 않기 위한 visit와 queue가 핵심입니다!