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

이번 포스트에서는 깊이 우선 탐색(DFS) 알고리즘에 대해 다루도록 하겠습니다.

깊이 우선 탐색(DFS)란?

: 루트 노드(혹은 임의의 노드)부터 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 넓게 탐색하기 전에 깊게 탐색하는 것입니다.

 

깊이 우선 탐색의 특징 :

• 재귀 알고리즘이다.
• 모든 형태의 트리 순회(traversals)는 깊이 우선 탐색의 종류이다.
• 어떤 노드를 방문했는지를 반드시 검사한다.
• 더 이상 방문할 노드가 없으면 이전 노드로 backtracking(다시 돌아가서 탐색하지 않은 정점이 있는지 확인)

깊이 우선 탐색의 동작 과정 : 

1. V0부터 시작해서 V0 방문
2. V0과 인접한 V1 방문
3. V1과 인접한 V3 방문
4. V3과 인접한 V7 방문
5. V7과 인접한 V4 방문
6. V4과 인접한 V1, V7은 이미 다 방문했으니 V7로 backtracking
7. V7과 인접한 V5 방문
8. V5과 인접한 V2 방문
9. V2과 인접한 V6 방문
10. 최종 결과 : V0, V1, V3, V7, V4, V5, V2, V6

깊이 우선 탐색 소스 코드 :

#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];

void dfs(int v)
{
    node_pointer w;
    visited[v] = TRUE;
    printf("%5d", v);
    for (w = graph[v]; w; w = w->link)
    	if(!visited[w->vertex])
        	dfs(w->vertex);
}

소스 코드 분석 :

만약 방문한 적이 없는 노드이면, 그 노드를 방문한다. 이 과정을 재귀적으로 실행하여 더 이상 방문할 노드가 없을 때까지 노드를 차례대로 방문합니다. 또한 이미 방문한 노드는 visited[v]를 TRUE로 변경하여 구분합니다.