BFS

" 탐색을 할 때 너비를 우선으로 탐색하는 알고리즘 "

---

목적

1. 임의의 정점에서 시작해서 모든 정점을 한 번씩 방문하는 것 (DFS와 동일)
2. 모든 가중치가 1일 때, 최단 거리를 구하는 알고리즘

---

조건

1. 최소 비용 문제
2. 간선의 가중치가 1이어야 한다
3. 정점과 간선의 개수가 적어야 한다

• 최소 비용의 의미 = 간선의 가중치

---

과정

---

구현 방법 (queue 사용)

1. 1을 큐에 넣는다.
2. 1을 큐에서 빼고, 인접한 2와 3을 큐에 넣는다.
3. 2를 큐에서 빼고, 인접한 4와 5를 큐에 넣는다.
4. 3을 큐에서 빼고, 인접한 6과 7을 큐에 넣는다.
5. 탐색하지 않은 노드가 없으므로 큐에 들어있는 값들 4, 5, 6, 7을 순서대로 뺀다.

---

구현 코드

#include<bits/stdc++.h>
#define MAX 100000
using namespace std;

bool check[MAX];
vector<int> v[MAX];

void BFS(int start) {
	check[start] = true;
	queue<int> q;
	q.push(start);

	while (!q.empty()) {	// 큐에 값이 있을 경우 반복
		int x = q.front();
		q.pop();
		cout << x << " ";
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (!check[y]) {
				q.push(y);
				check[y] = true;
			}
		}
	}
}

int main() {
	int t, n, m;
	int start = MAX;
	cin >> t;	 // 간선의 개수 주어짐
	for (int i = 0; i < t; i++) {
		cin >> n >> m;	// 정점끼리 연결
		v[n].push_back(m);
		v[m].push_back(n);
		if (start > n) {	// 시작점 정하기 위함
			start = n;
		}
	}
	BFS(start);
}

---

참조 사이트
https://dev.to/snird/breadth-first-traversal-for-binary-trees-in-js-h9m
https://hongku.tistory.com/156