[Algorithm] DFS 깊이 우선 탐색, BFS 너비 우선 탐색 (C++)

DFS : Depth First Search (깊이 우선 탐색)

시작 노드부터 시작하여 다음 Branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

모든 노드를 방문 하고자 하는 경우에 사용한다.

재귀함수를 이용하여 구현한다. 여기서 주의해야 할 점은

방문 여부를 반드시 검사해야 한다.

 

이러한 무방향 그래프를 1부터 시작해서 DFS로 탐색하겠다.

 

#include<iostream>
#include<vector>


using namespace std;

bool visit[9];
vector<int> node[9];

void dfs(int start_node) {
	visit[start_node] = true;
	cout << start_node << " ";
	for (int i = 0; i < node[start_node].size(); i++)
	{
		int not_find = node[start_node][i];
		if (!visit[not_find])
			dfs(not_find);
	}
}
int main(void) {
	// 1와 2 연결
	node[1].push_back(2);
	node[2].push_back(1);

	// 1와 3 연결
	node[1].push_back(3);
	node[3].push_back(1);

	// 1와 8 연결
	node[1].push_back(8);
	node[8].push_back(1);

	// 3와 4 연결
	node[3].push_back(4);
	node[4].push_back(3);

	// 3와 5 연결
	node[3].push_back(5);
	node[5].push_back(3);

	// 4와 5 연결
	node[4].push_back(5);
	node[5].push_back(4);

	// 4와 5 연결
	node[2].push_back(7);
	node[7].push_back(2);

	// 8와 7 연결
	node[7].push_back(8);
	node[8].push_back(7);

	// 7와 6 연결
	node[7].push_back(6);
	node[6].push_back(7);

	dfs(1);

	return 0;
}

 

BFS :  Breath First Search (너비 우선 탐색)

시작 노드부터 시작하여 인접한 노드를 먼저 탐색하는 방법

두 노드 사이의 최단 경로나 임의 경로를 찾을 때 사용한다.

 Queue, 노드 방문여부를 이용한다.

 

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

using namespace std;
int visit[9];
vector<int> node[9];

void bfs(int start_node) {
	queue<int> q;
	q.push(start_node);
	visit[start_node] = true;
	while (!q.empty()) {
		int find = q.front();
		q.pop();
		cout << find << " ";
		for (int i = 0; i < node[find].size(); ++i) {
			int not_find = node[find][i];
			if (!visit[not_find]) {
				q.push(not_find);
				visit[not_find] = true;
			}
		}
	}
}
int main(void) {
	// 1와 2 연결
	node[1].push_back(2);
	node[2].push_back(1);

	// 1와 3 연결
	node[1].push_back(3);
	node[3].push_back(1);

	// 1와 8 연결
	node[1].push_back(8);
	node[8].push_back(1);

	// 3와 4 연결
	node[3].push_back(4);
	node[4].push_back(3);

	// 3와 5 연결
	node[3].push_back(5);
	node[5].push_back(3);

	// 4와 5 연결
	node[4].push_back(5);
	node[5].push_back(4);

	// 4와 5 연결
	node[2].push_back(7);
	node[7].push_back(2);

	// 8와 7 연결
	node[7].push_back(8);
	node[8].push_back(7);

	// 7와 6 연결
	node[7].push_back(6);
	node[6].push_back(7);

	bfs(1);

	return 0;
}