[Algorithm] Depth-first-search (깊이 우선 탐색)

깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

 

출처 : 위키백과

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

예)

 

1) 1을 방문처리하며 스택에 넣는다.

 

 

2) 1과 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

 

3) 2와 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

4) 4와 인접한 정점이 없으므로, 스택에서 pop한다.

 

5) 스택에 가장 최근에 탐색한 정점인 2부터 다시 탐색한다.

    2와 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

6) 5와 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

7) 8과 인점한 정점이 없으므로 스택에서 pop한다.

 

8) 스택에 가장 최근에 탐색한 정점인 5부터 다시 탐색한다.

    5와 인접한 정점이 없으므로 스택에서 pop한다.

 

9) 스택에 가장 최근에 탐색한 정점인 2부터 다시 탐색한다.

    2와 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

10) 6과 인점한 정점이 없으므로 스택에서 pop한다.

 

11) 스택에 가장 최근에 탐색한 정점인 2부터 다시 탐색한다.

    2와 인접한 정점이 없으므로 스택에서 pop한다.

 

12) 스택에 가장 최근에 탐색한 정점인 1부터 다시 탐색한다.

    1와 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

13) 3과 인접한 정점이 있으면 스택에 넣고 방문처리한다.

 

14) 7과 인접한 정점이 없으므로 스택에서 pop한다.

 

15) 스택에 가장 최근에 탐색한 정점인 3부터 다시 탐색한다.

     3과 인접한 정점이 없으므로 스택에서 pop한다.

 

16) 스택에 가장 최근에 탐색한 정점인 1부터 다시 탐색한다.

     1과 인접한 정점이 없으므로 스택에서 pop한다.

     스택에 남아있는 정점이 없으므로 종료한다.