[알고리즘/탐색] BFS 너비 우선 탐색

너비 우선 탐색?

그래프 완전 탐색 방법 중 하나.

시작 노드에서 출발해 시작노드를 기준으로 가까운 노드 먼저 방문하며 탐색하는 알고리즘

 

노드 수 : V, 에지 수 : E 일 때

시간 복잡도 : O(V+E) 

 

구현 시 Queue 자료구조를 이용한다.

 

 

백준 1260번

https://www.acmicpc.net/problem/1260

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

std::vector<std::vector<int>> edges;
std::vector<bool> visited;

void DFS(int node)
{
	if (visited[node])
	{
		return;
	}
	std::cout << node << " ";
	visited[node] = true;
	for (const int& i : edges[node])
	{
		DFS(i);
	}
}

void BFS(int node)
{
	std::queue<int> queue;
	visited[node] = true;
	queue.push(node);

	while (!queue.empty())
	{
		std::cout << queue.front() << " ";
		for (const int& i : edges[queue.front()])
		{
			if (!visited[i])
			{
				visited[i] = true;
				queue.push(i);
			}
		}
		queue.pop();
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M, S;
	std::cin >> N >> M >> S;

	edges.resize(N+1,std::vector<int>());
	visited.resize(N + 1, false);
	while (M--)
	{
		int s, e;
		std::cin >> s >> e;
		edges[s].push_back(e);
		edges[e].push_back(s);
	}
	for (std::vector<int>& vec : edges)
	{
		std::sort(vec.begin(), vec.end());
	}


	DFS(S);
	visited = std::vector<bool>(N+1,false);
	std::cout << "\n";
	BFS(S);

}