[알고리즘 #4] 깊이 우선 탐색

깊이 우선 탐색

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

• 기능 : 그래프 완전 탐색

• 특징 : 재귀함수로 구현, 스택 자료구조 이용

• 시간 복잡도(노드 수 → V, 에지 수 → E) : O(V + E)

• 스택 오버플로에 유의하기

깊이 우선 탐색의 핵심 이론

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

3. 스택 자료구조에 값이 없을 때 까지 반복