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

BFS 알고리즘 (Breath First Search)

 

너비 우선 탐색 (BFS)은 큐 자료구조를 사용하여 너비를 우선적으로 탐색하는 탐색 알고리즘입니다. 흔히 최단 경로를 파악하여 최단 길이를 찾아낼 때 활용합니다. 순회의 순서로만 보면 이진 트리의 레벨 순회와 유사한 방식입니다.

위와 같은 이진 트리에 대하여 너비 우선 탐색을 해보겠습니다.

너비 우선 탐색은 기본적으로 '노드를 큐에넣고 -> 꺼내서 출력하고 -> 인접한 노드를 큐에넣고' 를 반복하는 알고리즘입니다. 가장 먼저 방문하는 노드1을 큐에 넣고 방문 완료(visited)합니다. 

큐에 들어있던 1을 꺼내서 출력하고 인접해있던 노드 2와 3을 큐에 넣고 방문 완료합니다. 

큐에서 먼저들어온 2를 꺼내서 출력하고 인접해있던 노드 4와 5를 큐에 넣고 방문 완료합니다. 

큐에서 먼저들어온 3을 꺼내서 출력하고 인접해있던 노드 6과 7을 큐에 넣고 방문 완료합니다. 

모든 노드가 방문처리 되었으므로 큐에 들어있던 나머지 노드들은 들어온 차례대로 출력되고 BFS 탐색이 종료됩니다.

 

알고리즘 구현

// Algorithm Analysis
// 너비 우선 탐색 (Breath First Search)

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

using namespace std;

int num = 7; // 전체 노드 수
int visited[8]; // 방문 체크용 배열. [0]은 미 사용
vector<int> arr[8]; // 인접한 노드를 연결할 배열

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

	}
}
int main() {
	arr[1].push_back(2);
	arr[2].push_back(1);

	arr[1].push_back(3);
	arr[3].push_back(1);

	arr[2].push_back(3);
	arr[3].push_back(2);

	arr[2].push_back(4);
	arr[4].push_back(2);

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

	arr[3].push_back(6);
	arr[6].push_back(3);

	arr[3].push_back(7);
	arr[7].push_back(3);

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

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

	bfs(1);
}

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.