깊이 우선 탐색(DFS)

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

stack을 이용하여 갈 수 있는 만큼 최대한 깊이 가는 것이고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아간다는 것

주로 반복문(Stack) / 재귀문(순환 알고리즘)을 통하여 구현된다.

 

🟩 방법

그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다.

 

1. 현재 노드를 방문한 것으로 표시

2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색

3. 더 이상 방문하지 않은 정점이 없으면 이전 정점을 역추적

4. 모든 정점을 방문할 때까지 프로세스 반복

 

 

🌟 반복 구현 (Stack 활용)

1) 시작 정점 A를 스택에 넣고 방문 처리한다. A
2) 스택의 최상단 노드 A는 꺼내 출력하고, 그 인접 노드인 C, B를 스택에 넣고 방문처리한다.(위 그림과 같이 직관적인 순서로 나타내기 위해 알파벳 역순으로 스택에 삽입하였다.) C B
3) 스택의 최상단 노드인 B는 꺼내 출력하고, 그 인접 노드인 E, D를 스택에 넣고 방문처리한다. C E D
4) 스택의 최상단 노드인 D는 꺼내 출력하고, 그 인접 노드인 I, H를 스택에 넣고 방문처리한다. C E I H
5) 스택의 최상단 노드인 H는 꺼내 출력한다. 방문하지 않은 인접 노드가 없으므로 스택에는 아무것도 넣지 않는다. C E I
6) 위 과정을 스택에 아무것도 남지 않을 때까지 반복한다.

 

🟩 시간 복잡도

N = 노드(정점)의 수, E = 간선의 수

 

인접 행렬에서 시간 복잡도 : O(N^2)

DFS 하나에 반복문을 V만큼 돌기 때문에, O(V) 시간이 필요하다. 

정점을 방문할 때마다 DFS를 부르는데, V개의 정점을 모두 방문하므로, 전체 시간 복잡도는 O(V^2)

 

인접 리스트에서 시간 복잡도 : O(N + E)

DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다.

전체 DFS가 다 끝난 이후를 생각해보면, DFS가 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 O(N+E)의 시간이 걸린다고 할 수 있다. 

 

🟩 장점

현재 경로 상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 든다.

너비 우선 탐색(BFS)보다 좀 더 간단하다.

목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

🟩 단점

검색 속도 자체는 BFS에 비해 느림

 

해가 없는 경우 무한 루프에 빠질 수 있다.

👉 실제의 경우 미리 지정한 깊이까지만 탐색하고, 목표 노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

 

얻어진 해가 최단 경로가 된다는 보장이 없다.

👉 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 뜻

 

🟩 활용

1. 경로의 특징을 저장해둬야 하는 문제 (경로 상의 노드를 기억해야 하는문제)

2. 검색 대상 그래프가 큰 문제