DFS(depth first search)

그래프 순회 방법 중 한가지

BFS가 너비(breadth)라면, DFS는 깊이(depth) 우선 탐색이기 때문에

정점에서 가장 멀리 떨어진 곳을 먼저 탐색한다.

 

주로 재귀를 통해 구현하기 때문에 백트래킹과 유사점을 갖는다.

 

DFS 진행은 4단계로 나눌 수 있다.

1. 현재 정점과 인접한 간선들을 본다.

2. 해당 간선으로 통하는 정점을 방문했는지 본다.

3. 방문하지 않았으면 방문한다.

4. 막혔으면 되돌아간다.

 

다음 그래프를 DFS로 탐색하는 순서다. 왼쪽 간선부터 탐색하는 방법이다.

또한, 방향이 없는 무방향 그래프이다.

진행 순서를 붙이니 좀 지저분해 보이지만, 피보나치 수열을 재귀로 진행했을 때와 같다.

그래프 상태

 

빨간 선은, 방문할 정점이 있는 노드로 호출되는 방향이다.

파란 선은, 갈 곳이 더 없기 때문에 함수가 return되면서, 상위 노드로 올라가는 방향이다.

 

 

배열로 표현하면 다음과 같다.

무방향 그래프기 때문에, 상위 노드도 포함시켰다.

만약 방향 그래프로 한다면, 상위 노드에 대한 정보는 생략하면 된다.

 

리스트로 표현하면 다음과 같다.

 

시간 복잡도

 

인접 행렬이냐, 인접 리스트냐에 따라 다르다.

 

정점이 V (그래프의 원)

간선이 E (정점끼리 이어져 있는 선) 이라 하면

 

인접 행렬과 인접 리스트 모두 정점이 한 번씩 호출된다. O(V)

 

인접 행렬의 경우, 모든 정점들과 간선이 있는지 확인해야 한다.

왜냐하면, 3번 노드와 연결되면 현재 노드 배열의 3번 index에 표시를 한 것 처럼

연결된 노드의 value에 해당하는 현재 노드 배열 index를 봐야하기 때문이다.

따라서, 매 정점마다 V번의 탐색이 일어난다.

따라서, 시간 복잡도는 O(V * V)가 된다.

 

인접 리스트의 경우, 연결된 정점의 Index가 value로 들어가 있어서

해당 노드에 연결된 간선만큼(E) 탐색한다.

현재는 무방향 그래프기 때문에, 간선이 기본 2개지만, 방향 그래프라면

4번 같은 노드는 간선을 하나만 가진다.

따라서, 시간 복잡도는 O(V + E)가 된다.

 

인접 행렬 vs 인접 리스트

보통은 인접 리스트로 하는 게 좋다.

왜냐하면, 정점의 개수 V가 커질 수록

V * V 만큼의 배열을 만들어야 하기 때문에, 공간 낭비가 발생하고

매 노드마다 V번 탐색을 해야 하기 때문에 V가 100,000 개만 되도, 전부 탐색하는데 1초가 걸린다.

(10억번 loop 도는데 1초로 간주했음)

 

그래도 굳이 인접 행렬의 장점을 꼽자면

배열로 만들었기 때문에, 데이터 접근에 상수 시간 O(1)이 소모된다.

 

자바나, 다른 언어에서 리스트가 간접 접근이기 때문에, 배열보다 접근 시간이 느리지만,

이 차이 보다는 V가 커지면서 순회 비용이 늘어나는게 더 크다.

 

DFS를 써야할 때

개인적인 기준이다.

트리의 지름같이, 인접 노드 신경 쓰지 않고 최대한 멀리 가는게 우선일 때 사용한다.