[알고리즘] 탐색 - BFS

BFS : queue를 사용하여 구현

시간복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V * V)
• DFS 처럼 Sparse Graph 일 때 인접 리스트 사용이 효율적이다.

 

BFS 구현을 위한 그래프

1 -> 2  -> 3 -> 4 -> 5 -> 6 -> 7

 

1. queue의 front의 노드를 기준으로 연결된 간선이 있고, 방문하지 않은 노드를 찾는다.

2. 조건에 맞는 노드들은 모두 큐에 넣는다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void bfs(int start, vector<vector<int>> graph, vector<bool> check) {
	queue<int> q;
	int current_node, next_node;
	q.push(start);
	check[start] = true;

	while (!q.empty()) { // queue가 비어 있을 때까지 반복
		current_node = q.front();
		q.pop();
		printf("%d ", current_node);

		for (int i = 0; i < graph[current_node].size(); i++) {
			int next = graph[current_node][i];
			if (!check[next]) { // 아직 방문하지 않은 노드라면..
				check[next] = true; // 방문 완료 표시
				q.push(next);
			}
		}
	}
}

int main() {
	int N, M, start;
	int u, v;
	vector<vector<int>> graph;
	vector<bool> check;

	cin >> N >> M >> start;
	
	graph.resize(N + 1);
	check.resize(N + 1);

	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	bfs(start, graph, check);

	return 0;
}

Sample Input	Sample Output
5 5 3 5 4 5 2 1 2 3 4 3 1	3 1 4 2 5

 

BFS를 이용할 수 있는 문제

1. 최소 비용 문제
2. 간선의 가중치가 1이다. 
3. 간선의 개수가 적다.