[그래프] 깊이 우선 탐색 (DFS - Depth First Search) 알고리즘

 

학습 목표

깊이 우선 탐색 (Depth First Search) 개념, 예시, 의의

깊이 우선 탐색 개념

1) 정의

깊이 우선 탐색이란, 트리 구조나 그래프 데이터 구조를 탐색하는 알고리즘이다.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

깊이 우선 탐색은 스택 구조를 사용한다.

 

2) 동작 예시 

 

시작 노드에서부터 왼쪽이 우선 선택되었다고 가정하자.

(1) 탐색 시작 노드를 스택에 삽입하고 '방문' 처리한다.

(2) 방문하지 않은 인접 노드를 스택에 넣고 방문처리 한다.

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

>> 방문할 수 있는 노드는 모두 방문 후, 없으면 돌아간다는 의미이다.

     (이 때 스택에서 추가되었던 값들이 하나씩 다시 제거된다.)

(3) (2)번 과정을 반복하여 수행될 수 없을 때 멈춘다. 이 때 스택은 아무것도 없게 된다.

 

아래 트리 구조는 숫자와 같이 탐색된다.

 

3) 의의 

탐색 알고리즘 중 하나의 방식으로 해당 방식은 스택 데이터 구조를 사용된다.

얕은 그래프 탐색에서는 목표까지 노드를 더 많이 거쳐야될 수 있다. 반대로, 깊은 목표 지점까지 가야한다면 더 효율적으로 목표를 탐색할 수 있다.

 

Reference

이것이 취업을 위한 코딩 테스트다.

Depth First Search (DFS) Algorithm (programiz.com)