학습 목표
-
DFS 알고리즘이 무엇인지 이해한다.
-
DFS 알고리즘의 동작 과정을 이해한다.
-
DFS 알고리즘을 소스코드로 구현한다.
깊이 우선 탐색(DFS, Depth-First Search) 알고리즘이란?
그래프 탐색 알고리즘입니다. 그래프 탐색 알고리즘은 그래프 내 모든 정점을 방문하는 방법입니다. DFS는 이름에서 알 수 있듯이 깊이를 우선시하는 탐색 알고리즘입니다. 다시 말해, 한 정점에서 연결된 간선을 살펴보면서 방문 가능한 정점이 있다면, 즉시 방문하는 방식으로 동작하는 알고리즘입니다.
위에서 언급했듯이 방문 가능한 정점이 있으면 바로 방문합니다. 이 동작 방식은 재귀 호출을 사용하여 구현하면 간단하게 구현됩니다. 정점을 방문하는 과정을 함수 호출, 더 이상 방문할 정점이 없을 경우 이전 정점으로 돌아오는 과정을 함수 리턴으로 생각해 구현합니다.
탐색 과정
알고리즘의 동작 과정은 다음 세 단계로 이루어집니다.
1. 탐색 시작 정점을 방문합니다.
2. 현재 정점(또는 시작 정점)에서 연결된 간선을 순차적으로 탐색합니다.
-
탐색 중인 정점이 방문한 정점이라면, 다음 정점을 확인합니다.
-
탐색 중인 정점이 방문하지 않은 정점이라면 이 정점을 방문하여 2번 과정을 진행합니다.(재귀 호출)
3. 더 이상 방문할 정점이 없다면 탐색을 끝냅니다.(함수 리턴)
소스 코드(인접 행렬)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <stdio.h>
#define TRUE 1
#define FALSE 0
bool visited[6];
int g[6][6]; //양방향 그래프
void addEdge(int u, int v) {
g[u][v] = 1;
g[v][u] = 1;
}
void dfs(int nowVertex) {
printf("정점 %d 를 방문했습니다.\n", nowVertex);
//방문 표시
visited[nowVertex] = TRUE;
//방문하지 않은 정점 조사
for (int i = 0; i < 6; i++) {
//연결되어 있고, 방문하지 않았다면
if (g[nowVertex][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
int main() {
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 5);
for (int i = 0; i < 6; i++) {
if (!visited[i]) {
dfs(i);
}
}
return 0;
}
|
시간 복잡도
시간 복잡도 분석을 위해 두 가지 그래프 형태를 고려하겠습니다. 우선, 주어진 그래프가 인접 리스트일 경우에는 모든 정점을 확인하는 복잡도인 |V|, 각 정점에서 연결된 간선들을 확인하는 과정에서 |E| 만큼 소요됩니다. 따라서 인접 리스트 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|+|E|) 만큼의 시간 복잡도를 보입니다.
그래프가 인접 행렬 형태로 주어진다면 각 정점에서 연결된 간선들을 확인하는데 |V| 만큼 시간 복잡도가 필요합니다. 따라서 인접 행렬 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|^2) 만큼의 시간 복잡도를 보입니다.
정리
-
그래프 상의 모든 정점을 깊이 우선 방식으로 탐색하는 알고리즘이다.
-
방문 가능한 정점이 있다면 즉시 방문하는 방식으로 동작한다.
-
동작 원리를 고려해 재귀 함수로 구현하면 간단하다.
-
시간 복잡도는 인접 리스트로 구현 시 O(|V|+|E|), 인접 행렬로 구현 시 O(|V|^2)이다.
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] - 너비 우선 탐색(BFS) #10 (0) | 2020.07.26 |
|---|---|
| [알고리즘] - 그래프의 표현 방법 #8 (0) | 2019.03.13 |
| [알고리즘] - 합병 정렬(Merge sort) #7 (2) | 2019.02.06 |
| [알고리즘] - 퀵 정렬(Quick sort) #6 (0) | 2019.01.31 |
| [알고리즘] - 선택 정렬(Selection sort) #5 (0) | 2019.01.16 |
