DFS, BFS 구현 방법

코드랑 원리를 아예 다 외워버리자!!!

 

출처: <[C++] 어서와! 자료구조와 알고리즘은 처음이지?> 강의 - 그래프 - 02. 그래프 순회: DFS와 BFS

 

 

1. DFS 구현: 재귀 이용

 

 

 

2. DFS : 스택 이용

• 함수 반환값( vector<int> )은 dfs 함수에서 정점들이 방문한 순서를 정수형 벡터 형태로 반환
• visited: 각각 정점 방문 여부 기록
• visit_order: 각각 정점 방문 순서 기록

 

 

3. BFS : 큐 이용

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

using namespace std;

const int N = 6;
bool gVisited[N] = {};

void dfs_recursion(const vector<vector<int>>& adj_list, int s)
{
	if (gVisited[s])
		return;

	gVisited[s] = true;
	cout << s << ", ";

	for (int v : adj_list[s])
		dfs_recursion(adj_list, v);
}

vector<int> dfs(const vector<vector<int>>& adj_list, int s)
{
	vector<bool> visited(adj_list.size(), false);
	vector<int> visit_order;
	stack<int> stk;
	stk.push(s);

	while (!stk.empty()) {
		int v = stk.top();
		stk.pop();

		if (visited[v])
			continue; // 이미 방문했으면 스킵!

		visited[v] = true; // 정점 v를 방문
		visit_order.push_back(v);

		for (int a : adj_list[v]) {
			if (!visited[a])
				stk.push(a);
		}
	}

	return visit_order;
}

vector<int> bfs(const vector<vector<int>>& adj_list, int s)
{
	vector<bool> visited(adj_list.size(), false);
	vector<int> visit_order;
	queue<int> q;
	q.push(s);

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

		if (visited[v])
			continue; // 이미 방문했으면 스킵!

		visited[v] = true; // 정점 v를 방문
		visit_order.push_back(v);

		for (int a : adj_list[v]) {
			if (!visited[a])
				q.push(a);
		}
	}

	return visit_order;
}

int main()
{
	vector<vector<int>> adj_list = {
		{1, 3, 4},
		{0, 2, 4},
		{1, 5},
		{0, 4},
		{0, 1, 3},
		{2}
	};

	cout << "dfs_recursion: ";
	dfs_recursion(adj_list, 0);
	cout << endl;

	auto dfs_order = dfs(adj_list, 0);
	auto bfs_order = bfs(adj_list, 0);

	cout << "dfs: ";
	for (auto n : dfs_order)
		cout << n << ", ";
	cout << endl;

	cout << "bfs: ";
	for (auto n : bfs_order)
		cout << n << ", ";
	cout << endl;
}