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

 

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

- 해가 존재할 가능성이 있으면 계속해서 같은 방향으로 탐색하는 알고리즘이다.

- 스택 구조( 재귀 )를 이용한다.

- 진행 중이던 방향이 막혀 있을 경우 이전으로 되돌아가서 위의 과정을 반복한다.

- 모든 곳을 방문했을 때 탐색을 종료한다.

- 넓은 트리에 효과적이나 목표 노드가 없는 경로에 깊이 빠질 수 있는 단점이 있다.

[ Fig. 1 ] DFS 탐색 순서

 

1. 동작 원리

(1) 현재(초기) 노드를 방문으로 표시한다.

(2) 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있는지 탐색한다.
(3) (2)의 조건에 맞는 노드를 탐색하면, 해당 노드를 중심으로 (1 - 2) 과정(재귀)을 반복한다.

(4) 방문하지 않은 노드가 없을 경우 종료한다.

2. 함수 구현

#include <stdio.h> #define MAX 6 #define VISITED 2 #define ADJACENCY 1 int G[MAX][MAX] = // init adjacency matrix {{0,1,1,0,0,0}, {1,0,0,1,1,0}, {1,0,0,0,0,1}, {0,1,0,0,0,0}, {0,1,0,0,0,0}, {0,0,0,0,1,0}}; int visit[MAX]; // to check whether visited or not char vc[MAX+1] = {"ABCDEF"}; // allocate alphabets to each vertical. void dfs( int); int main( void) {  dfs( 0); // call function with a starting vertical. } /*  Depth First Search function  - this function uses recursion to search root. */ void dfs( int v) {  int i;  visit[v] = VISITED; // mark this vertical as VISITED.  for( i = 0 ; i < MAX ; i ++)  {   // find a adjacency vertical that have never visited before   if( !visit[i] && G[v][i] == ADJACENCY)   {    // if find the vertical, mark it as VISITED.    visit[i] = VISITED;    printf("%c에서 %c로 이동\n", vc[v], vc[i]);    // recall this function with the vertical.    dfs( i);   }  } }

3. 실행 결과

Fig.1 의 그래프를 기준으로 작성한 결과,  A > B > D > E > C > F 순으로 탐색하였다.