깊이 우선 탐색(DFS)

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

탐색을 하는 데 있어 깊은 것을 우선적으로 하여 탐색하는 알고리즘.

 

스택이 사용되지만, 컴퓨터는 구조적으로 시스템 스택 프레임의 원리를 사용하기때문에 스택을 사용하지 않아도 재귀적으로 구현이 가능함.

 

1. 시작 노드를 스택에 삽입하고, 방문 처리한다.
2. 스택의 최상단 노드를 확인한다.
3. 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺀다.
4. 2, 3의 과정은 스택이 비어질때까지 반복된다.

 

 

#include <iostream>
#include <vector>
using namespace std;

int n = 7;
int checked[7];
vector<int> arr[8];

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

int main() {
	// 연결된 노드들을 나타내고, 인접 노드도 표현. 
	arr[1].push_back(2);
	arr[2].push_back(1);
	
	arr[1].push_back(3);
	arr[3].push_back(1);
	
	arr[2].push_back(3);
	arr[3].push_back(2);
	
	arr[2].push_back(4);
	arr[4].push_back(2);
	
	arr[2].push_back(5);
	arr[5].push_back(2);
	
	arr[3].push_back(6);
	arr[6].push_back(3);
	
	arr[3].push_back(7);
	arr[7].push_back(3);
	
	arr[4].push_back(5);
	arr[5].push_back(4);
	
	arr[6].push_back(7);
	arr[7].push_back(6);
	
	dfs(1);
	return 0;
}