[알고리즘] DFS (깊이 우선 탐색)

DFS(Depth First Search, 깊이 우선 탐색)는 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 입니다.

현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동합니다. 

이 과정을 반복하다가 더 이상 반복할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 

이 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘 입니다. 

 

(출처: 삼성 코드 그라운드)

 

즉,

1) 특정한 순서대로  정점을 계속 방문하다가,

2) 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서

3) 해당 정점에서 방문할 수 있는 정점을 탐색하는 방법입니다. 

 

 

이미지 출처: 삼성 코드그라운드

 

[자료구조]

필요한 자료구조로는,

- 해당 정점이 방문되었는지 확인하는 boolean 혹은 int 타입의 1차원 배열 visited[]

- 정점들의 집합, 정점과 정점 사이의 연결을 확인할 수 있는 간선들의 집합 (그래프의 구현은 인접행렬 방식, 인접리스트 방식이 존재합니다.)

 

[시간복잡도]

모든 정점을 방문하며 모든 간선을 검사하기 때문에 시간복잡도는 O(V+E)가 됩니다. 

(V: 정점의 개수, E: 간선의 개수)

 

[슈도 코드]

 

출처: 학교 알고리즘2 수업시간

 

(color[] 배열은 현재 위치의 방문 여부를 판별하기 위한 배열로 없어도 되지만, 이 배열로 그래프가 cycle을 이루는지에 대한 여부를 판결할 수 있습니다.  속성으로는 WHITE(방문 안함), GRAY(현재 방문 중), BLACK(이미 방문함))

 

[C코드]