[알고리즘] 깊이 우선 탐색(DFS : Depth-First Search)

깊이 우선 탐색이란?

 - 루트 노드 혹은 다른 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

 

깊이 우선 탐색과정

 

0에서 부터 시작해서 노드 번호가 작은 순서로 간다.

먼저 0 부터 시작해서 인접한 노드 중 작은 것 먼저 방문한다. 즉 1을 방문한다.

그 다음 1과 인접한 노드 중 작은 것을 방문한다. 즉 3을 방문한다.

다음과 같이 진행하면 탐색 순서는 0 -> 1 -> 3 -> 4 -> 2 -> 5 가 된다.

 

DFS

 

깊이 우선 탐색 장점

 - 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

 - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

깊이 우선 탐색 단점

 - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

 - 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

* 위키백과 참고

 

깊이 우선 탐색 특징 

 - 스택을 이용하여 그래프를 순회함

 - 스택 =  선행관계

   : 나를 먼저 방문하고 그 다음으로 인접한 노드를 차례로 방문

      (단, 방문해던 노드는 방문하지 않음)

 - 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함

 

깊이 우선 탐색 구현

  - DFS(V, Visited)  //v는 시작점, visited는 방문한 노드기록

    1. v를 방문했다고 처리한다.

    2. v와 인접한 모든 w에 대하여 다음을 반복

    3. 만약 w를 방문하지 않았다면, DFS(w,visited)  //w는 이웃

    5. 방문순서 반환

  - 구현: 재귀함수 -> 스택사용