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

너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

 

너비 우선 탐색은 '최단 경로'를 찾아준다는 점!

 

준비물은 큐

 

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

using namespace std;

int number = 7;
int checked[7];

vector<int> a[8];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	checked[start] = true;

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		printf("%d ", x);

		for (int i = 0; i < a[x].size(); i++) 
		{
			int y = a[x][i];
			if (!checked[y])
			{
				q.push(y);
				checked[y] = true;
			}
		}
	}
}

int main(void)
{
	a[1].push_back(2);
	a[2].push_back(1);

	a[1].push_back(3);
	a[3].push_back(1);

	a[2].push_back(3);
	a[3].push_back(2);

	a[2].push_back(4);
	a[4].push_back(2);

	a[2].push_back(5);
	a[5].push_back(2);

	a[4].push_back(5);
	a[5].push_back(4);

	a[3].push_back(6);
	a[6].push_back(3);

	a[3].push_back(7);
	a[7].push_back(3);

	a[6].push_back(7);
	a[7].push_back(6);

	bfs(1);

	return 0;
}

 

관련 유투브 주소 : https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16