DFS (Depth First Search) #

DFS (Depth First Search, 깊이우선탐색)는 BFS (Breath First Search, 너비우선탐색) 와 더불어 Tree를 조사하는 가장 기본적인 알고리즘 중 하나로 Root Node를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법(자식우선탐색)이다. 이렇듯 깊이를 우선적으로 탐색하기 때문에 그래프의 최대 경로가 정해져 있거나, 깊이를 예측할 수 있는 경우에 주로 사용된다.

더 이상 방문할 정점이 없을 때 최근 분기점으로 돌아오는 로직은 Stack 또는 재귀함수(Recursive Function)를 이용해 구현한다. 이와 달리 BSF는 Queue를 이용하여 구현한다.

DFS 알고리즘 #

Stack을 이용한 DFS 알고리즘

1. 시작 정점(Root Node)를 push
2. Stack에서 노드 하나를 pop
3. Stack에서 꺼낸 노드가 아직 방문하지 않은 노드라면 방문 표시 후 인접 노드를 push
4. Stack에 남은 노드가 없을 때까지 2,3 단계를 반복

Recursive Function을 이용한 DFS 알고리즘

1. Parameter로 넘어온 노드가 이미 방문한 노드인경우 return 하도록 stop condition 설정
2. Parameter로 넘어온 노드가 방문하지 않은 노드인 경우 방문 표시
3. 인접 노드에 대해 재귀적으로 함수를 호출하며 탐색 진행

DFS의 장·단점 #

DFS 장점 #

• 현 경로상의 노드만 기억하면 되므로 공간 복잡도의 비용 저하
• 목표 노드가 깊은 단계에 있을 경우 비교적 빠른 시간내에 탐색 가능

DFS 단점 #

• 목표 노드가 없는 경로가 깊은 depth인 경우 탐색이 오래 걸릴 수 있음
• 얻어진 목표 노드까지의 경로가 최단 경로라는 보장이 없음

DFS 시간복잡도 #

DFS는 그래프의 모든 간선을 조회한다. 그래프의 구성요소를 노드(N)와 간선(E)으로 표현했을 때 구현 방법에 따른 시간복잡도는 다음과 같다.

1. 인접리스트 : 모든 노드를 탐색하는 최악의 경우를 제외한 나머지 경우 인접행렬보다 빠른 시간복잡도 O(N+E)
2. 인접행렬 : 노드의 수가 적은 경우에 사용하는 것을 추천. N개의 노드에 대해 행렬의 크기가 N*N만큼 차지하기에 시간복잡도는 O(N^2)

Suggested Pages #

• 0.025 자료구조
• 0.013 포인터
• 0.013 인덱스
• 0.013 재귀적 형태
• 0.013 Vertex
• 0.013 노드
• 0.013 Graph
• 0.013 변
• 0.013 Linked List
• 0.013 Edge
• More suggestions...