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

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 BFS(너비 우선 탐색)입니다. 

 

정의 

• 그래프에서 어떤 노드에 인접한 노드를 모두 탐색한 뒤, 탐색된 노드를 순서대로 접근하여 인접한 노드를 탐색하는 것을 반복하여 탐색하는 알고리즘 

동작 과정 

1. 현재 노드를 방문처리한다.
2. 현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 전부 큐같은 공간에 순서대로 저장한다.   
3. 저장된 노드 중 가장 첫번째 노드를 현재노드로 하고 큐에서 제거한다. 
4. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 

 

구현

// 시간복잡도는 O(노드수 + 간선수)이다. 

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

using namespace std:

bool visited[9];
vector<int> graph[9];

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 < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

 

이상으로 BFS에 관한 내용을 마치겠습니다. 

읽어주셔서 감사합니다.