(2021.07.19)
자구 7주차 과제랑 연결
깊이 우선 탐색 (Depth First Search)
깊이 우선탐색 (DFS) 은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 탐색할 수 없을 때, 그 전의 정점으로 돌아가 다른 방향의 간선으로 탐색을 하는 순회방법이다.
탐색 과정에서 후입 선출 구조의 스택을 사용한다.
1. 배열을 False로 초기화하고 공백 스택을 생성한다.
2. 정점 A를 시작으로 탐색을 시작한다.
3. 정점 A에 탐색할 정점 B,C가 있으므로 스택에 push 하고 정점 B를 탐색한다.
4. 정점 B에 탐색할 정점 D가 있으므로 스택에 push하고 정점 D를 탐색한다.
5. 정점 D에 탐색할 정점 G가 있으므로 스택에 push하고 정점 G를 탐색한다.
6. 정점 G에 탐색할 정점 E,F가 있으므로 스택에 push하고 정점 E를 탐색한다.
7. 정점 E에 탐색할 정점 C가 있으므로 스택에 push하고, 정점 C를 탐색한다.
8. 정점 C에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 E에 탐색할 정점이 있는지 확인한다.
9. 정점 E에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 G에 탐색할 정점이 있는지 확인한다.
10. 정점 G에 탐색할 정점 F가 있으므로 스택에 push하고 정점 F를 탐색한다.
11. 정점 F에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 G에 탐색할 정점이 있는지 확인한다.
12. 정점 G에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 D에 탐색할 정점이 있는지 확인한다.
13. 정점 D에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 B에 탐색할 정점이 있는지 확인한다.
14. 정점 B에 탐색할 정점이 없으므로 스택을 pop하여 받은 정점 A에 탐색할 정점이 있는지 확인한다.
정점 A에서 탐색할 정점이 없으므로 스택을 pop하면, 스택이 공백이므로 깊이 우선 탐색을 종료한다.
깊이 우선 탐색으로 순회한 경로는 아래와 같다.
