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

학습 목표

• DFS 알고리즘이 무엇인지 이해한다.

• DFS 알고리즘의 동작 과정을 이해한다.

• DFS 알고리즘을 소스코드로 구현한다.

 

깊이 우선 탐색(DFS, Depth-First Search) 알고리즘이란?

 그래프 탐색 알고리즘입니다. 그래프 탐색 알고리즘은 그래프 내 모든 정점을 방문하는 방법입니다. DFS는 이름에서 알 수 있듯이 깊이를 우선시하는 탐색 알고리즘입니다. 다시 말해, 한 정점에서 연결된 간선을 살펴보면서 방문 가능한 정점이 있다면, 즉시 방문하는 방식으로 동작하는 알고리즘입니다. 

 

 위에서 언급했듯이 방문 가능한 정점이 있으면 바로 방문합니다. 이 동작 방식은 재귀 호출을 사용하여 구현하면 간단하게 구현됩니다. 정점을 방문하는 과정을 함수 호출, 더 이상 방문할 정점이 없을 경우 이전 정점으로 돌아오는 과정을 함수 리턴으로 생각해 구현합니다.

 

탐색 과정

알고리즘의 동작 과정은 다음 세 단계로 이루어집니다.

 

1. 탐색 시작 정점을 방문합니다.

2. 현재 정점(또는 시작 정점)에서 연결된 간선을 순차적으로 탐색합니다.

• 탐색 중인 정점이 방문한 정점이라면, 다음 정점을 확인합니다.

• 탐색 중인 정점이 방문하지 않은 정점이라면 이 정점을 방문하여 2번 과정을 진행합니다.(재귀 호출)

3. 더 이상 방문할 정점이 없다면 탐색을 끝냅니다.(함수 리턴)

 

 

 

 

소스 코드(인접 행렬)

#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)이다.