Depth First Search(깊이 우선 탐색)

Depth First Search은 Breath First Search와는 다르게 이진트리의 맨 하단까지 내려가서 search를 하는 것을 우선적으로 하는 탐색이다.
stack형 구조를 가지고 있다는 것이 특징이다. 하지만 stack을 사용하지 않고도 구현은 가능하다.

Depth First Search Code

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

vector<int> a[8];
int c[8];

void dfs(int x)
{	
	if(c[x]) return;
	c[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[2].push_back(1);
	
	a[1].push_back(3);
	a[3].push_back(1);
	
	a[2].push_back(3);
	a[3].push_back(2);
	
	a[2].push_back(4);
	a[4].push_back(2);
	
	a[2].push_back(5);
	a[5].push_back(2);
	
	a[3].push_back(6);
	a[6].push_back(3);
	
	a[3].push_back(7);
	a[7].push_back(3);
	
	a[6].push_back(7);
	a[7].push_back(6);
	
	dfs(1);
	
	return 0;
}

주의사항

위 코드에서 1,2,3,6,7,4,5 인 이유는
제 1 노드는 2,3 노드와
제 2 노드는 1,3,4,5노드와 연결되어 있는데
1노드가 2노드를 방문한 다음 제 2노드는 1노드를 방문했으니 그 다음 노드인 제 3노드를 방문하는 것이다.

이미지 출처
자료 출처