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

DFS와 다르게 너비 즉 인접한 항목을 우선적으로 탐색하는 알고리즘으로 흔히 길찾기에 가장 많이 쓰인다.

위 그래프를 0번 기준으로 BFS를 사용한다고 하면 0번은 연결되어있는 1->3->5를 순회한 후에 1번과 연결된 4번과 6번을 탐색하고, 3번으로 가서 7번을 탐색하는 순서로 순회할 것이고 최종적인 순서는 (물론 구현을 어떻게 하느냐에 따라 순서는 달라질 수 있지만 기본적으로 연결된 노드를 우선으로 탐색한다는 것은 변함이 없다)

0->1->3->5->4->6->7->2의 순서가 될 것이다.

vector<vector<int>> vec;
vector<bool> discovered;

void BFS(int n)
{
	discovered[n] = true;
	queue<int> _queue;
	_queue.push(n);

	while (_queue.empty() == false)
	{
		int now = _queue.front();
		_queue.pop();
		cout << "visited : " << now << endl;

		for (int& there : vec[now])
		{
			if (discovered[there] == true)
				continue;

			_queue.push(there);
			discovered[there] = true;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	vec = vector<vector<int>>(8, vector<int>(8, 0));
	discovered = vector<bool>(8, false);

	vec[0].push_back(1);
	vec[0].push_back(3);
	vec[0].push_back(5);
	vec[1].push_back(4);
	vec[1].push_back(6);
	vec[2].push_back(3);
	vec[3].push_back(7);
	vec[4].push_back(1);
	vec[5].push_back(4);
	vec[5].push_back(6);
	vec[6].push_back(2);
	vec[6].push_back(4);
	vec[7].push_back(1);
	vec[7].push_back(6);

	BFS(0);

	return 0;
}