[2021 하계 모각코] 6차시

깊이 우선 탐색

 

 

루트 노드에서 시작해서 해당노드의 자식노드를 먼저 탐색하는 방법이다.

한방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행한다.

즉 넓게 탐색하기 전에 깊게 탐색하는 것이다.

​

모든 노드를 탐색하는 경우 사용하며 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다. 단순 검색 속도는 너비 우선 탐색이 더 빠르다.

​

 

---

 

---

구현 방법

​

스택을 사용하여 방문한 노드를 담고 최근 방문한 노드를 pop하여 해당 노드의 자식노드를 스택에 담는다.

이 과정을 반복하며 깊이 우선 탐색을 진행한다.

​

 

---

시간 복잡도

​

- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

​

* 인접 리스트로 표현된 그래프 : O(N+E)

* 인접 행렬로 표현된 그래프 : O(N^2)