깊이 우선 탐색(Depth First Search) _ 재귀호출

깊이 우선 탐색(Depth First Search) _ 재귀호출

• 맹목적으로 각 vertex를 탐색할 때 주로 사용

• 더이상 나아가지 못할때 까지 깊이 탐색하면서 나아감

• Binary Search Tree의 재귀호출로 순회하는 함수(InOrder, PreOrder, PostOrder)들이 대표적인 예가 될 수 있다

• 스택(Stack) 또는 재귀 호출이 사용된다.

재귀 호출 DFS 알고리즘 순서

1.시작점으로 vertex를 인자로 DFS 함수 호출

2.해당 vertex를 방문했다는 사실을 기록

3.해당 vertex와 인접하고 방문하지 않은 vertex를 인자로 DFS 함수를 호출

2~3 과정이 모든 vertex들을 방문할때까지 되풀이 된다.

 

위 그래프의 인접행렬을 이차원배열로 표현한뒤, DFS또한 구현하여 실행해봤다.

 

 

코드

constexpr int VERTEX_COUNT = 8;
constexpr int adj[VERTEX_COUNT][VERTEX_COUNT] =
{
	{0, 1, 1, 0, 0, 0, 0, 0}, //v0  : v1, v2
	{1, 0, 0, 1, 1, 0, 0, 0}, //v1  : v0, v3, v4
	{1, 0, 0, 0, 0, 1, 1, 0}, //v2  : v0, v5, v6
 	{0, 1, 0, 0, 0, 0, 0, 1}, //v3  : v1, v7
	{0, 1, 0, 0, 0, 0, 0, 1}, //v4  : v1, v7
	{0, 0, 1, 0, 0, 0, 0, 1}, //v5  : v2, v7
	{0, 0, 1, 0, 0, 0, 0, 1}, //v6  : v2, v7
	{0, 0, 0, 1, 1, 1, 1, 0}  //v7  : v3, v4, v5, v6
};

bool visited[VERTEX_COUNT]; //방문기록

void DFS_Recursive(int _start)
{
	visited[_start] = true; //방문
	printf("%d 방문\n", _start);
	for (int i = 0; i < VERTEX_COUNT; i++)
	{
		if (adj[_start][i] == 1 && !visited[i])//인접했다 && 방문안했다 
		{
			DFS_Recursive(i); //재귀호출, 인접한 vertex를 인자로 대입
		}
	}
}

int main()
{
	DFS_Recursive(0); 
	return 0;
}

실행결과

빨간색 화살표는 재귀호출이 시작되는것, 노란색은 재귀호출이 끝나고 원래 호출했던 함수로 돌아가는것(rewind)

실행결과를 보면 화살표 번호 순서대로 방문하는 것을 알 수 있다.

이과정을 자세히 들여다보면 처음 시작은 0부터 시작하므로 0을 인자로 넣어서 V0을 방문 V0에서 인접하며, 방문하지 않은 V1발견, V1을 인자로 재귀호출을 시작하게 된다. 아래 순서 번호는 곧 위 그림의 화살표 번호과 같다.

1. V1을 방문, V1에서 인접하며, 방문하지 않은 V3발견, V3을 인자로 재귀호출                                        현재 누적 방문 : V0, V1                                                                                                             

2. V3을 방문, V3에서 인접하며, 방문하지 않은 V7발견, V7을 인자로 재귀호출                                                        현재 누적 방문 : V0, V1, V3                                                                                                                         

3. V7을 방문, V7에서 인접하며, 방문하지 않은 V4발견, V4을 인자로 재귀호출                                    현재 누적 방문 : V0, V1, V3, V7                                                                                                  
4. V4을 방문, V4에서 인접하며, 방문하지 않은 vertex가 없으므로 재귀호출 하지 않고 함수가 끝남          현재 누적 방문 : V0, V1, V3, V7, V4                                                                                           
5. V7을 인자로 가졌던 함수로 돌아감(rewind), V7에서 인접하며 방문하지 않은 V5발견, V5을 인자로 재귀호출                                                                                                                           현재 누적 방문 : V0, V1, V3, V7, V4                                                                                                                                                                                                                                                                                                                                                                     
6. V5을 방문, V5에서 인접하며, 방문하지 않은 V2발견, V2을 인자로 재귀호출                                     현재 누적 방문 : V0, V1, V3, V7, V4, V5                                                                                         
7. V2을 방문, V2에서 인접하며, 방문하지 않은 V6발견, V6을 인자로 재귀호출                                    현재 누적 방문 : V0, V1, V3, V7, V4, V5, V2                                                                              
8. V6을 방문, V6에서 인접하며, 방문하지 않은 vertex가 없으므로 재귀호출 하지 않고 함수가 끝남 이때부터는 모두 방문했으므로 rewind 되는 것만 남음                                                                  현재 누적 방문 : (모두 방문 완료)V0, V1, V3, V7, V4, V5, V2, V6                                                                                                                                                                                      
9. V2을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
10. V5을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
11. V7을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
12. V3을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
13. V1을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
14. V0을 인자로 가졌던 함수로 돌아감(처음 호출했던 함수), 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남