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++로 나타낸 코드입니다. (리스트 방식)

#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);
}

다음은 Java로 나타낸 코드입니다. (행렬 방식)

import java.util.*;

public class Main {
    static boolean edge[][];
    static boolean visited[];
    static int n;
    static int m;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        edge = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            edge[u][v] = true;
        }
        dfs(1);
    }

    public static void dfs(int cur) {
        visited[cur] = true;
        System.out.print(String.valueOf(cur) + ' ');
        for (int i = 1; i <= n; i++) {
            if (visited[i] || !edge[cur][i]) continue; // already visited or not connected.
            dfs(i);
        }
    }
}

다음 시간엔 그래프에 대해 알아보겠습니다.