BFS (Breadth First Search)

BFS(너비 우선 탐색)란 그래프를 탐색하는 방법 중 하나로 현재 정점으로부터 인접한 모든 정점들을 먼저 방문 하는 알고리즘이다.

BFS 특징

<aside> 💡

복잡도 (정점 수 : V , 간선 수 : E)

</aside>

• 시간 복잡도 (인접 리스트) : O(V + E)
• 시간 복잡도 (인접 행렬) : O(V^2)
• 공간 복잡도 : O(V)

<aside> 💡

장점

</aside>

• 너비를 우선으로 탐색하므로 최단 경로를 얻을 수 있다.
• 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다

<aside> 💡

단점

</aside>

• DFS와 달리 queue를 이용하여 탐색할 정점들을 저장하므로 더 큰 메모리 공간이 필요하다.

BFS 구현

queue 를 이용해 구현할 수 있다.

1. 탐색 시작 노드를 queue 에 삽입하고 방문 처리한다.
2. queue 에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 queue 에 삽입 후 방문 처리한다.
3. 2번 과정을 반복하다 queue 가 비게되면 탐색을 종료한다.

초기 그래프 및 간선 정보

시작 노드 queue에 삽입 및 방문 처리

1번 노드와 인접한 노드 탐색, 방문 여부 확인 후 queue에 삽입 및 방문처리

2번 노드와 인접한 노드 탐색, 방문 여부 확인 후 queue에 삽입 및 방문처리

3, 4번 노드와 인접한 노드 탐색, 방문 안한 노드가 없으므로 queue에서 제거

5번 노드와 인접한 노드 탐색, 방문 여부 확인 후 queue에 삽입 및 방문처리

6번 노드와 인접한 노드 탐색, 모든 노드 탐색 후 queue가 비었으므로 탐색 종료

BFS 코드

• 인접 리스트를 이용해 구현하기

std::vector<std::vector<int>> Graph; // 인접 리스트로 구현된 그래프
std::vector<bool> bVisited; // 방문 여부

void BFS(int Start)
{
	std::queue<int> Q;

	int Now = Start;
	bVisited[Now] = true;
	Q.push(Now);

	while (!Q.empty())
	{
		Now = Q.front();
		Q.pop();
		
		for (int i = 0; i < static_cast<int>(Graph[Now].size()); ++i)
		{
			int Next = Graph[Now][i];
			if (!bVisited[Next])
			{
				Q.push(Next);
				bVisited[Next] = true;
			}
		}
	}
}

• 인접 행렬로 구현하기 (좀 더 직관적이나 복잡도 측면에서 비효율적)

std::vector<std::vector<int>> Graph; // 인접 행렬로 구현된 그래프
std::vector<bool> bVisited; // 방문 여부

void BFS(int Start)
{
	std::queue<int> Q;

	int Now = Start;
	Q.push(Now);
	bVisited[Now] = true;

	while (!Q.empty())
	{
		Now = Q.front();
		Q.pop();
		
		for (int i = 0; i < static_cast<int>(Graph.size()); ++i)
		{
			if (0 == Graph[Now][i])
			{
				continue;
			}

			if (!bVisited[i])
			{
				Q.push(i);
				bVisited[i] = true;
			}
		}
	}
}

아래의 코드는 다음 그래프를 BFS를 통해 노드들을 탐색하고, 방문한 노드를 출력하는 코드이다.

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

int main() 
{
	std::vector<std::vector<int>> Graph(7, std::vector<int>(0, 0));
	std::vector<bool> bVisited(7, 0);

	// 인접 리스트 그래프 생성
	Graph[1].push_back(2);
	Graph[1].push_back(3);

	Graph[2].push_back(1);
	Graph[2].push_back(4);
	Graph[2].push_back(5);
	
	Graph[3].push_back(1);

	Graph[4].push_back(2);

	Graph[5].push_back(2);
	Graph[5].push_back(6);

	Graph[6].push_back(5);

	// BFS
	std::queue<int> Q;

	int Now = 1;
	Q.push(Now);
	bVisited[Now] = true;

	while (!Q.empty())
	{
		Now = Q.front();
		Q.pop();

		std::cout << "방문 노드 : " << Now << std::endl;

		for (int i = 0; i < static_cast<int>(Graph[Now].size()); ++i)
		{
			int Next = Graph[Now][i];
			if (!bVisited[Next])
			{
				Q.push(Next);
				bVisited[Next] = true;
			}
		}
	}

	return 0;
}

방문 노드 : 1
방문 노드 : 2
방문 노드 : 3
방문 노드 : 4
방문 노드 : 5
방문 노드 : 6