[자료구조] 14. DFS

Depth First Search(DFS)는 그래프 탐색 방식중 하나이다. DFS의 방식은 분기점이 생겼을시, 우선 무시하고 한 방향의 끝에 다다를때 까지 진행한 후, 하나의 경로를 완전히 탐색했으면, 분기점으로 돌아가 분기점을 탐색하는 방식이다.

구현

시작 정점 v에서 출발하여, 다음과 같은 과정을 거친다.

1. 현재 정점이 VISITED라면 재귀를 종료하고 다시 돌아가기

2. 현재 정점을 VISITED로 설정(중복 방문을 막기 위하여)

3. 연결되어 있는 다른 정점 탐색

4. 연결된 모든 다른 정점에 대하여 해당 알고리즘 반복

용어

unvisited vertex: 아직 방문하지 않은 정점

visited vertex: 방문한 정점

unvisited edge: 아직 방문하지 않은 간선

discovery edge: 방문한 간선으로, 해당 간선으로 진행하여 새로운 정점을 찾은 경우.

back edge(역방향 간선): 방문한 간선으로, 해당 간선으로 진행하였지만, 이미 방문한 정점이였던 경우.

효율

정점과 간선에 접근하고, VISITED인지 확인하거나 VISITED로 라벨을 변경하는것에 O(1) 시간이 소요된다.

즉, n개의 정점과 m개의 간선을 가진 그래프에서 DFS는 O(n + m)의 시간 복잡도를 가진다.

응용

경로찾기

스택을 이용하여 방문한 경로를 저장하는 방식으로 구현한다. DFS의 특성상 가장 가까운 경로는 아닐 수 있다.

사이클 탐색

DFS를 이용하여 시작정점과 도착정점이 같은 경로인 cycle(사이클)이 존재하는지 확인할 수 있다. 사이클이 존재한다는 것은 역방향 간선이 존재한다는 것과 동치인데, 이를 통해서 DFS를 진행하며 역방향 간선이 존재하는지 탐색하는 것을 통하여 사이클이 존재하는지 판별한다.