BFS(너비우선탐색)

BFS(Breadth Fist Search)

-탐색 순서로 폭을 우선적으로 함

-노드로부터 같은 거리에 있는 인접 노드를 모두 탐색함

-이러한 특성 때문에 목적까지의 최단 경로(Shortest Path)를 찾을 수 있게 됨

-Queue를 사용

-안 가본 노드가 없을 때까지 모든 노드를 방문하는 소모적 탐색의 방법 중 하나

 

BFS 규칙

1. 인접 노드가 여러 개 있을 경우 보통 알파벳 순서로 먼저 접근함

 

탐색 순서 예시

 

1.시작노드 A의 인접노드인 B,G를 탐색 , 이때 Queue Front(Queue의 첫번째 원소)를 제거하고 B,G를 순서대로 Queue에 삽입

 

2. 그다음 B와 G의 인접노드인 C,E,H탐색, 마찬가지로 Queue Front를 제거하고 C,E,H를 Queue에 삽입

 

 

이러한 작업을 반복하면서 Queue에서 제거된 노드를 순차적으로 나열하면 너비우선 탐색 순서가 됨

 

 

<코드 예시>

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

//그래프의 인접리스트 표현
std::vector<std::vector<int>> adj;

std::vector<int> Bfs(int start)
{
	//정점 발견했는지 여부
	std::vector<bool> discovered(adj.size(), false);
	//방문할 예정인 정점
	std::queue<int> q;
	//방문한 순서
	std::vector<int> order;
	
	q.push(start);
	discovered[start] = true;
	
	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		order.push_back(here);

		for (int i = 0; i < adj[here].size(); ++i)
		{
			int there = adj[here][i];
			if (!discovered[there])
			{
				q.push(there);
				discovered[there] = true;
			}
		}
	}

	return order;
}