[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

DFS란? DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다.

DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다. DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다.

DFS 예시 위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다.

가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다. 이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다.

(C노드를 먼저 방문해도 된다. 순서는 상관 없다) 이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다.

이후 스택.....