[알고리즘] DFS, BFS의 구현

다른 블로그에서 dfs와 bfs를 설명하는 글이 많지만 dfs를 재귀로만 구현하는 경우가 대부분입니다.  재귀의 사용은 스택의 사용과 동일하여 그렇게 해도 되지만, 스택만으로 구현하는 방법도 포스팅하고자 합니다. (주석 참고)

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>

using namespace std;

int N, M, V;
vector<int> v[1001];
bool check[1001] = { false };

void dfs(int s) {
	
	check[s] = true;
	cout << s << " ";
	vector<int> vec = v[s];

	for (int i = 0; i < vec.size(); i++) {
		if (!check[vec[i]]) {
			dfs(vec[i]);
		}
	}

}
/*
void dfs_stack(int s) {
	stack<int> stack;
	check[s] = true;
	stack.push(s);
	cout << s << " ";
	
	while (!stack.empty()) {
		int n = stack.top();

		vector<int> vec = v[n];
		for (int i = 0; i < vec.size(); i++) {
			if (!check[vec[i]]) {
				check[vec[i]] = true;
				cout << vec[i] << " ";
				stack.push(vec[i]);
				break;
			}
			else if (i == vec.size() - 1) {
				stack.pop();
			}
		}
	}
}
*/

void bfs(int s) {

	queue<int> q;
	check[s] = true;
	q.push(s);
	cout << s << " ";

	while (!q.empty()) {
		int n = q.front();
		q.pop();

		vector<int> vec = v[n];
		for (int i = 0; i < vec.size(); i++) {
			if (!check[vec[i]]) {
				check[vec[i]] = true;
				cout << vec[i] << " ";
				q.push(vec[i]);
			}
		}
	}

}

int main(void) {

	int a, b;
	cin >> N >> M >> V;

	/*using list*/
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[b].push_back(a);
		v[a].push_back(b);
	}

	dfs(V);
	cout << endl;
	memset(check, false, sizeof(check));
	bfs(V);
	
	

	return 0;
}