[자료구조] 그래프 - BFS(Breadth First Search)

BFS(Breadth First Search)

• 그래프의 너비를 우선시하여 탐색하는 알고리즘
• 하나의 정점에서 시작하여 그 정점에 연결된 간선들 모두를 탐색하고 나서 다음 정점을 탐색한다.
• 큐를 이용해서 발견된 정점들부터 차례로 탐색을 진행한다.

코드

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

	queue<int> q;
	q.push(here);
	discovered[here] = true;

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

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited : " << here << endl;

		for (int there = 0; there < 6; there++)
		{
			if (adjacent[here][there] == 0)
				continue;
			if (discovered[there])
				continue;

			q.push(there);
			discovered[there] = true;

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