📚 목차
요약
1. 깊이 우선 탐색 (DFS; Depth-Frist Search)
1. 깊이 우선 탐색(DFS)
- 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
| 기능 |
특징 |
시간 복잡도(노드 수: V, 에지 수: E) |
| 그래프 완전 탐색 |
1. 재귀함수로 구현 |
|
- 스택 자료구조 이용 | O(V+E) |
2. 깊이 우선 탐색의 핵심 이론
- 원본 그래프를 인접 리스트로 표현하기
- 시작점부터 노드를 하나씩 스택에 넣어서 방문 배열을 체크한다.
- 방문한 노드를 POP하고 POP한 노드의 인접 노드를 PUSH한다.
