9. DFS(깊이 우선 탐색)

DFS(깊이 우선 탐색)

DFS는 깊이 우선 탐색을 뜻합니다. 이 DFS 또한 맹목적으로 각 노드를 탐색할 때 주로 사용됩니다. DFS는 자료구조로 stack을 사용해서 구현됩니다. 하지만 사실 스택을 안쓰고 재귀함수로도 구현이 가능합니다. 이유는 컴퓨터 자체가 구조적으로 항상 스택의 원리를 이용하기 때문입니다.

DFS 과정

1. 시작 노드 스택에 삽입
2. 시작 노드 방문 처리
3. 스택 최상단 노드 확인
4. 최상단 노드에 방문 하지 않은 인접 노드 있으면 그 노드를 스택에 넣고 방문 처리 / 없으면 최상단 노드 빼기

• 3,4번 과정을 스택이 빌 때까지 반복

#include <iostream>
#include <vector>

using namespace std;

int number = 7;
int visited[8];
vector<int> a[8];

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

int main() {
	a[1].push_back(2);
	a[1].push_back(3);

	a[2].push_back(1);
	a[2].push_back(3);
	a[2].push_back(4);
	a[2].push_back(5);

	a[3].push_back(1);
	a[3].push_back(2);
	a[3].push_back(6);
	a[3].push_back(7);

	a[4].push_back(2);
	a[4].push_back(5);

	a[5].push_back(2);
	a[5].push_back(4);

	a[6].push_back(3);
	a[6].push_back(7);

	a[7].push_back(3);
	a[7].push_back(6);
	
	dfs(1);

	return 0;
}