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

BFS란?

▶ 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

▶ 최단 경로를 찾아주기 때문에 최단 길이를 보장해야 하는 경우에 자주 사용되는 알고리즘

 

BFS 구현 방법:

1. 시작 노드를 큐에 삽입

2. 시작 노드 방문 처리

3. 큐에서 하나의 노드를 꺼냄

4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입

5. 3-4 반복

 

 

아래와 같은 그래프가 있다고 치자!

위에 적어둔 BFS 구현 방법을 그림으로 알아보자.

참고로 방문 처리는 그래프에서 빨갛게 칠하는 걸로 나타냈다. 

 

 

 

1. 시작 노드를 큐에 삽입

2. 시작 노드 방문 처리

▶ 시작 노드인 1을 큐에 삽입하였고, 방문 처리 

 

 

3. 큐에서 하나의 노드를 꺼냄

4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입

▶ 큐에서 1을 꺼내고, 1에 연결된 2와 3을 큐에 삽입

▶ 그 후, 방문 처리

 

 

3. 큐에서 하나의 노드를 꺼냄

4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입

▶ 큐에서 2를 꺼내고, 2의 인접 노드인 4와 5를 차례대로 큐에 삽입

▶ 그 후, 방문 처리

 

 

 

3. 큐에서 하나의 노드를 꺼냄

4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입

▶ 큐에서 3을 꺼내고, 3의 인접 노드인 6과 7을 차례대로 큐에 삽입

▶ 그 후, 방문 처리

 

 

모든 노드가 방문처리 되었으니 큐에 있는 노드들을 차례대로 꺼내주면 끝

1 - 2 - 3 - 4 - 5 - 6 -7 순서로 방문 완료

 

아래 코드는 위 그림 예제를 구현한 것!

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

using namespace std;

int number = 7;
int c[7];
vector <int> a[8];

void bfs(int start) {
	queue <int> q;
	q.push(start);
	c[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x<<" ";
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!c[y]) {
				q.push(y);
				c[y] = true;
			}
		}
	}
}

int main() {
	a[1].push_back(2);
	a[2].push_back(1);
	
	a[1].push_back(3);
	a[3].push_back(1);
	
	a[2].push_back(3);
	a[3].push_back(2);
	
	a[2].push_back(4);
	a[4].push_back(2);

	a[2].push_back(5);
	a[5].push_back(2);

	a[3].push_back(6);
	a[6].push_back(3);
	
	a[3].push_back(7);
	a[7].push_back(3);

	a[4].push_back(5);
	a[5].push_back(4);

	a[6].push_back(7);
	a[7].push_back(6);

	bfs(1);

	return 0;
}

 

 

 

참고 영상: 

https://youtu.be/66ZKz-FktXo?si=MPvJzrCytB25MUVn