[탐색] 깊이 우선 탐색, DFS(Depth First Serch)

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://www.youtube.com/watch?v=lFtQnOhKnr0&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=20 

---

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

 

그래프 완전 탐색 기법 중 하나

그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는  알고리즘

 

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
그래프 완전 탐색	- 재귀 함수로 구현 - 스택 자료구조 이용	O(V + E)

 

실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 함

단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에 응용할 수 있음

 

DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 리스트가 필요하며, 그래프는 인접 리스트로 표현할 수 있음

1. 시작할 노드를 정한 후 스택에 시작점을 삽입, 방문 여부 표시
2. 스택의 값을 pop 한 후 탐색 순서에 기록, 삭제한 값의 인접 노드(인접 리스트를 통해 확인)에 대하여 방문 여부 확인 후 방문하지 않았다면 스택에 삽입, 방문 여부 표시
3. pop한 값에 인접 노드가 없다면 다음 스택 값 pop 하여 2번 진행
4. 스택에 남은 값이 없을 때까지 반복