[c++] BFS와 DFS

BFS, DFS란? 

그래프를 탐색하는 방법으로는 BFS와 DFS가 있다. BFS(Breadth-First Search)는 너비우선탐색이고, DFS(Depth-First Search)는 깊이우선탐색이다. BFS는 최대한 옆으로 넓게 이동하는 방법으로, 더이상 옆으로 갈 수 없을때 아래로 이동하기때문에 너비우선탐색으로 불린다. 루트노드와 제일 인접한 노드서부터 차례대로 탐색을 하기때문에 주로 두 노드사이의 최단경로를 찾을때 많이 사용되고 큐를 이용하여 구현된다. DFS는 최대한 아래로 이동하는 방법으로, 더이상  내려갈때가 없을때 다른 브랜치로 넘어가 탐색하기때문에 깊이우선탐색으로 불린다. 주로 미로찾기 문제, 모든 노드를 방문하고자 하는 경우에 사용되며, BFS보다는 성능이 떨어지지만 코드는 조금 간단하다.  BFS는 재귀함수 또는 스택으로 구현된다. 

BFS

DFS

 

구현 코드 

1) BFS

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

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

	while (!que.empty()) {
		int tmp = que.front();
		que.pop();
		cout << tmp<<" ";
		for (int i = 0; i < graph[tmp].size(); i++) {
			if (check[graph[tmp][i]] == false) {
				que.push(graph[tmp][i]);
				check[graph[tmp][i]] = true; //방문
			}
		}
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;

	vector <vector <int>> graph(n + 1);
	vector <bool> check(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) { //node값에 순차접근
		sort(graph[i].begin(), graph[i].end());
	}
	bfs(start, graph, check);

	

}

 

2) DFS (재귀함수 이용) 

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

using namespace std;

void dfs(int start, vector < vector <int>>graph, vector <bool> check) {
	check[start] = true; //방문
	cout << start << " ";
	
	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];
		if (check[next] == false)
			dfs(next, graph, check);
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;

	vector <vector <int>> graph(n + 1);
	vector <bool> check(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) { //node값에 순차접근
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(start, graph, check);
}

 

3) DFS ( 스택 이용) 

#include <iostream>
#include<vector>
#include <stack>
#include <algorithm>

using namespace std;

void dfs(int start, vector<vector<int>>graph, vector<bool>check) {
	stack<int> s;
	s.push(start);
	check[start] = true;
	cout << start<<" ";

	while (!s.empty()) {
		int temp = s.top();
		s.pop();
		for (int i = 0; i < graph[temp].size(); i++) {
			int next = graph[temp][i];
			if (check[next] == false) {
				cout << next << " ";
				check[next] = true; //방문
				s.push(temp);
				s.push(next);
				break;
			}
		}
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;

	vector <vector <int>> graph(n + 1);
	vector <bool> check(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) { //node값에 순차접근
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(start, graph, check);
}

 

시간복잡도

BFS와 DFS모두 O(V+E)이다. (V: 정점 E: 간선)  인접리스트로 구현할 경우, 각 정점과 간선을 한번씩 방문하기 때문에 정점 + 간선 만큼의 시간이 걸린다. 

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS