[알고리즘] 스탠다드 BFS (너비 우선 탐색)

이 포스트는 너비 우선 탐색을 처음으로 접하는 분을 대상으로 합니다. 

너비 우선 탐색은 그래프에서 사용할 수 있는 알고리즘 입니다. 처음 이해를 하실 때는 저는
`퍼지는 방향으로` 의 키워드를 잡고 이해를 했습니다. 

Queue 를 사용을 하여 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> map;
vector<bool> visited;
int n, m;
int u, v;

void bfs(int a) {
	//bfs 는 기본적으로 queue 를 사용한다.
	queue<int> q;
	visited[a] = 1;
	q.push(a);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (visited[nx]) continue;
			visited[nx] = true;
			q.push(nx);
		}
	}
}

int main() {
	cin >> n >> m;
	map.resize(n + 1);
	visited.resize(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		map[u].push_back(v);
	}
	bfs(1);
}