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

깊이 우선 탐색 (DFS)

- 연결 graph, 무방향 graph

- stack 사용

 

 

단계

① 출발 정점 v 방문

② v에 인접하고 방문하지 않은 한 정점 w 선택

③ w를 시작점으로 다시 깊이 우선 탐색

④ 모든 인접 정점을 방문한 정점 u에 도달시, u를 방문하기 위해 사용된 간선 (w, u) 상의 정점 w로 되돌아감

⑤ 정점 w로부터 다시 깊이 우선 탐색

⑥ 방문 안된 정점으로 더 이상 갈 수 없을 때 종료

 

 

 

ex) 0 – 1 – 3 – 7 – 4 – 5 – 2 – 6 순으로 방문

 

 

분석

① 인접 리스트 사용

    리스트 node 수 2e개 만큼 조사 → O(e) 소요

② 인접 행렬 사용

    한 정점에 인접한 정점들 조사하는데에 O(n) 소요

    ∴ 전체 원소 조사 → O($n^2$) 소요