[Algorithm] 깊이 우선 탐색 (Depth First Search)

깊이 우선 탐색(DFS)이란?

깊이 우선 탐색(DFS)은 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘이다.
탐색 도중 더 방문할 정점이 존재하지 않으면 뒤로 돌아가서 다른 경로를 찾아간다.

탐색 과정

1. 시작 노드를 방문한다.
   • 방문한 노드는 체크한다.
2. 시작 노드와 인접한 노드들을 차례대로 탐색한다.
   • 인접한 노드를 기준으로 다시 DFS를 처음부터 실행한다.
3. 위 과정을 반복하여 모든 노드를 방문하면 종료한다.

구현

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

using namespace std;

int number = 5;
int check[5];
vector<int> a[6];

void dfs(int x) {
	if (check[x])
		return;
	
	check[x] = true;
	cout << x << " ";
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		dfs(y);
	}
}

int main() {
	// 0과 1을 연결
	a[0].push_back(1);
	a[1].push_back(0);

	// 0과 2를 연결
	a[0].push_back(2);
	a[2].push_back(0);

	// 0과 4을 연결
	a[0].push_back(4);
	a[4].push_back(0);

	// 1과 2를 연결
	a[1].push_back(2);
	a[2].push_back(1);

	// 2와 3을 연결
	a[2].push_back(3);
	a[3].push_back(2);

	// 3과 4를 연결
	a[3].push_back(4);
	a[4].push_back(3);

	// 2와 4를 연결
	a[2].push_back(4);
	a[4].push_back(2);
	
	dfs(0);

	return 0;
} 

참고

참고