Breath First Search(너비 우선 탐색)

Breath First Search는 너비를 기준으로 탐색을 수행하는 알고리즘입니다.
최단경로를 찾아주는 점에서 최단길이를 보장해야 할 때 많이 사용하며, queue를 활용하여 탐색을 수행합니다.
BFS는 1과 가까운 노드부터 탐색을 하는 알고리즘이며, 이것을 토대로 다른 알고리즘에 활용이 된다.

Breath First Search Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> a[8];
int c[8];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	
	while(!q.empty())
	{
		int x = q.front();
		c[x] = true;
		cout << x << ' ';
		q.pop();
		
		for(int i = 0 ; i < a[x].size() ; i++)
		{
			int y = a[x][i];
			if(!c[y])
			{
				q.push(y);
				c[y] = true;
			}
		}
	}
}

int main()
{
	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[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;
}

이미지 출처
자료 출처