- 탐색 시, 너비를 우선으로 탐색하는 기법으로 시작점과 가까운 것 위주로 탐색한다.
이러한 BFS의 특징은 맹목적 탐색 과 최단길이 보장이다.
0. Queue에 start 노드를 넣는다.
1. Queue에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드중 방분하지 않은 노드를 방문하여 차례대로 큐에 삽입한다.
3. 1-2 과정을 Queue에 요소가 남지 않을 때 까지 반복한다.
#include <iostream>
#include <vector>
#include <queue>
#define MAX_NODE INT_MAX
using namespace std;
bool visited[MAX_NODE]; // Queue의 요소에 접근하였다는 것을 알려주는 배열
vector<int> array[MAX_NODE + 1]; // 요소가 들어있는 vector graph
void bfs(int start)
{
queue<int> q; // BFS애 사용 될 Queue
q.push(start); // 먼저, Queue에 첫 번째 요소를 삽입한다.
visited[start] = true; // 첫 번째 요소에 방문처리 한다.
while(!q.empty())) // BFS를 통해 모든 요소를 방문하였을 때 방문을 종료한다. 만일, 특정 요소 탐색을 위한 것이라면 다른 조건을 넣어도 된다.
{
int x = q.front(); // Queue의 첫 번째 요소를 변수에 저장한다.
q.pop(); // Queue의 첫 번째 요소를 제거한다.
cout << x << endl; // Queue의 첫 번째 요소를 출력한다.
for(int i = 0; i < array[x].size(); i++) // 기존 그래프에서, Queue에서 제거된 요소에 연결된 노드를 찾는다.
{
int y = array[x][i]; // 연결된 노드를 y에 할당한다.
if(!visited[y]) // 만일 노드 y가 방문되지 않았다면
{
q.push(y); // Queue에 노드 y를 넣고
visited[y] = true; // 노드 y를 방문처리 한 뒤 상기 과정을 반복한다.
}
}
}
}
