[알고리즘] BFS(Breadth-First Search, 너비 우선 탐색) (C++)

 이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해 알아본다.

그래프에 대한 간단한 설명을 보고 오면 더 좋다.(https://085a.tistory.com/8)

• BFS 정의
• BFS 장,단점
• BFS 탐색 과정
• BFS 구현

BFS 정의

 BFS는 Breadth-First search의 약자로 너비 우선 탐색이라고 한다. 임의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 

---

BFS 장, 단점

BFS의 장점

• 해를 구할 때 최단 경로가 나온다.
• 노드의 수가 적고 깊이가 얕으면 빠른 탐색이 가능하다.

BFS의 단점

• DFS와 비교하면 더 큰 저장공간이 필요하다.

---

BFS 탐색 과정

 BFS가 그래프를 어떤 과정으로 탐색하는지 그림으로 확인해보자.

 위 그림처럼 생긴 그래프를 예시로 한다. 탐색을 시작할 노드는 루트 노드인 1번 노드로 한다.

(탐색 순서 = 1)

루트 노드인 1번 노드를 탐색하였다.

(탐색 순서 = 1, 2)

1번 노드의 자식노드인 2번 노드를 탐색하였다.

(탐색 순서 = 1, 2, 3)

 1번 노드와 인접한 3번 노드가 있기 때문에 3번 노드를 탐색하였다.

(탐색 순서 = 1, 2, 3, 4)

 더 이상 1번 노드와 인접한 노드가 없기 때문에 2번 노드와 인접한 4번 노드를 탐색하였다.

(탐색 순서 = 1, 2, 3, 4, 5)

 더 이상 2번 노드와 인접한 노드가 없고 3번 노드와 인접한 노드도 없기 때문에 4번 노드와 인접한 5번 노드를 탐색하였다.

(탐색 순서 = 1, 2, 3, 4, 5, 6)

 4번 노드와 인접한 노드인 6번 노드를 탐색하였다. 탐색 완료!

---

BFS 구현

 BFS는 queue를 사용하여 구현한다. 이 구현은 백준 1260: DFS와 BFS(https://www.acmicpc.net/problem/1260)를 기준으로 작성하였다.

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

using namespace std;

int N, M, V;
bool visited[1001];
vector<int> graph[1001];
queue<int> q; // 자식 노드를 저장할 queue인 q

void bfs(int start) {
	q.push(start); // 시작 노드를 q에 push
	visited[start] = true; // start번 노드 탐색
	while (!q.empty()) { // q가 empty일 때까지
		int s = q.front(); // q의 맨 앞 노드 번호를 s에 저장
		q.pop(); // 저장한 노드 pop
		cout << s << " "; // 저장(탐색)한 노드 출력 
		int size = graph[s].size(); // s번 노드의 자식 노드 수를 size에 저장
		for (int i = 0; i < size; i++) { // size만큼 반복
			int next = graph[s][i]; // s번 노드의 i번째 자식 노드를 next에 저장
			if (!visited[next]) { // next번 노드를 방문 안했으면
				q.push(next); // q에 next번 노드 저장
				visited[next] = true; // next번 노드 탐색
			}
		}
	}
}


int main() {
	cin >> N >> M >> V; // N: 노드의 수, M: 간선의 수, V: 탐색을 시작할 노드 번호
	for (int i = 0; i < M; i++) { // 데이터 입력
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) { // 번호가 작은 것 부터 방문하기 위해 정렬
		sort(graph[i].begin(), graph[i].end());
	}

	bfs(V); // V번 노드부터 bfs 실행

	return 0;
}

 탐색한 노드의 자식 노드를 queue에 저장하고 그 노드들 부터 탐색한다. 

N: 노드의 수, M: 간선의 수, V: 탐색을 시작할 노드의 번호

BFS 탐색 과정에서 예시로 든 그래프를 위 코드로 탐색하면 아래와 같은 결과가 나온다.

탐색 결과 : 1 2 3 4 5 6

---

잘못된 내용이 있다면 알려주세요!