깊이 우선 탐색(depth-first search: DFS)

DFS (Depth-First Search, 깊이 우선 탐색)

깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 은 정점으로 이동하는 것입니다.
이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이러한 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘이 DFS 알고리즘입니다. 여러분의 이해를 돕기 위해 움직이는 그림으로 그래프를 설명하도록 하겠습니다.

위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정을 하겠습니다. 이 때, 정점 1에서 깊이 우선 탐색을 하게 된다고 합시다.

먼저, 정점 1에서 연결된 간선들을 통해 연결된 정점을 확인하면 2,3,7이 연결되어 있습니다. 이 때,  정점의 번호가 작은 쪽을 방문한다는 규칙에 의해 2번으로 이동합니다. 2번 정점은 3,4로 이동할 수 있지만 규칙에 의해 3번으로 이동합니다. 이와 같은 식으로 규칙대로 이동하다보면 1-2-3-5-7-6-4와 같이 방문을 하게됩니다.

4번 정점에서는 3을 방문할 수 있으나 3번은 이미 방문된 정점이므로 이동할 수 없습니다. 그러면 4번에선 더 이상 이동할 수 있는 정점이 없으므로 6번으로 돌아갑니다. 6번에서도 5번으로 이동할 수 있지만, 이미 방문된 정점이므로 7번으로 돌아갑니다. 위와 같은 식으로 계속 돌아가다보면 1번으로 돌아가게 됩니다.

1번에서도 3,7로 이동할 수 있지만 이미 방문한 정점이므로 DFS는 끝나게 됩니다. 

해당 알고리즘을 구현하기 위해서는 해당 정점이 방문되었는지 확인하는 boolean타입의 1차원 배열과 정점들의 집합 그리고 정점과 정점 사이의 연결을 확인할 수 있는 간선 집합들이 필요합니다.

그리고 해당 알고리즘의 시간복잡도는 모든 정점을 방문하며 모든 간선을 검사하기 때문에 시간복잡도는 O(V+E)입니다. ( V: 정점의 개수, E: 간선의 개수)

그래프의 구현은 그래프 챕터에서 다뤘듯이 인접행렬 방식과 인접 리스트 방식이 존재합니다. 위 문서에서는 C와 JAVA 코드는 인접행렬 방식, C++코드는 인접 리스트 방식을 이용하여 DFS를 구현하도록 하겠습니다. 

입력	출력
첫 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v가 주어집니다.	입력에 따른 깊이 우선 탐색 결과를 출력합니다.
Sample Input	Sample output
7 11 1 2 1 3 1 7 2 3 2 4 3 5 4 3 5 7 6 5 7 6 6 4	1 2 3 5 7 6 4

< C 코드 >

#include <stdio.h>
int edge[1010][1010];
int visited[1010];
int u, v;
int N, M;
 
int dfs(int cur) {
    visited[cur] = 1;
    printf("%d ", cur);
    for (int i = 1; i <= N; i++) {
        // already visited or not connected.
        if (visited[i]!=0 || edge[cur][i] == 0 ) continue; 
        dfs(i);
    }
}
 
int main() {
    scanf("%d %d", &N,&M);
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &u, &v);
        edge[u][v] = 1; // u -> v edge connect
    }
    dfs(1);
}

< C++ 코드 >

#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<int> > edge;
vector<bool> visited;
int N, M;
int u, v;
 
void dfs(int cur) {
    visited[cur] = true;
    cout << cur << ' ';
    for (int i = 0; i < edge[cur].size(); i++) {
        int there = edge[cur][i];
        if (visited[there]) continue;
        dfs(there);
    }
}
 
int main() {
    cin >> N >> M;
    edge.resize(N + 1);
    visited.resize(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
    }
    dfs(1);
}

출처 : CodegroundNote