자료구조(그래프 탐색) - 깊이 우선 탐색(Depth-First Seach, DFS)

깊이 우선 탐색(Depth-First Seach, DFS)

1단계)

A를 시작점, G를 목표로 해서 탐색을 시작한다.

 

2단계)

A에서 도달할 수 있는 정점은 B,C,D이므로 다음 후보로 표시한다. 후보 중에서 하나의 정점을 선택한다. 선택기준은 후보중 가장 최근에(가장 늦게) 추가된 것입니다.

 

3단계)

 

동일 시점에 후보가 된 정점은 어느 것을 선택하든 상관 없다. 여기선 왼쪽에 있는 정점을 선택한다. 모두 동일한 시점에 후보가 됐으므로 B를 선택한다. 선택한 정점으로 이동한다. 현재 있는 B로 부터 도달 할 수 있는 E와 F를 새로운 후보로 추가한다.

 

4단계)

 

후보인 정점은 '후입선출(LIFO)'구조로 관리하므로 '스택'데이터 구조를 이용할 수 있다. 후보중에 가장 최근에 추가된 것은 E와 F이다. 이중에서 왼쪽에 있는 E를 선택한다. 선택한 정점으로 이동한다. 현재 있는 E에서 도달할 수 있는 K를 새로운 후보로 추가한다.

 

정리

동일한 작업을 목표에 도달하거나 모든 정점의 탐색이 끝날때 까지 반복한다. 지금 까지 살펴 본것과 같이 우선 탐색은 하나의 길을 깊이 있게(수직으로 )찾아가는 방식이다.

 

[출처 - 알고리즘 도감, 저 Moriteru Ishida]

https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631

‎알고리즘 도감