[Algorithm] DFS

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

 

그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로  탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다.

 

DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder traversal, inorder traversal, postorder traversal)과 유사한 형태를 가지게 되는데, 순회 탐색들과 다른 점은 그래프에서는 사이클이 발생할 수 있기 때문에, 이미 방문한 노드에 대해서는 visited 를 구현하여 방문 여부를 확인하는 방법으로 구현한다.

 

 

2. DFS 구현

 

DFS는 앞서 말한 것과 같이 순환 알고리즘 형태를 가지고 있는데, 이는 스택을 사용하여서 구현할 수 있다. 루트 노드를 스택에 저장한다. 이후 해당 노드의 한 방향으로 탐색을 진행하면서 방문한 노드를 순서대로 스택에 저장한다. 탐색을 진행하다가 인접한 정점 중 더이상 탐색하지 않은 정점이 없는 경우 스택에서 방문했던 정점을 pop 하여 해당 정점을 기준으로 다시 탐색을 진행한다. 더이상 스택에 남아있는 정점이 없는 경우 탐색을 종료한다.

 

이와 같은 방법을 통해서 스택을 명시적으로 사용해서 구현할 수 있는데, 대부분의 경우 구현의 편리함으로 인해서 재귀 (recursion)을 사용해서 구현하게 된다. 재귀 함수로 구현하게 되면 함수를 한번 호출하는 것이 스택의 한 노드를 쌓게 되는 과정과 같다고 생각하면 된다.

 

- Java를 이용한 DFS 구현

import java.util.Arrays;

import Algorithm.Graph.Graph;

public class DFS implements Graph {

    private int N;

    private boolean[] visited;

    private boolean[][] graph;

    public DFS(boolean[][] graph) {
        N = graph.length;
        this.visited = new boolean[N];
        this.graph = new boolean[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                this.graph[i][j] = graph[i][j];
            }
        }
    }

    # int[] result: 결과를 저장할 배열
    # int index: result 배열의 인덱스로 이번에 방문한 노드가 저장될 인덱스
    # int R: 이번에 탐색할 노드의 번호
    private int dfs(int[] result, int index, int R) {
        for(int i = R; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(!graph[i][j] || visited[j])
                    continue;
                visited[j] = true;
                result[index++] = j;
                index = dfs(result, index, j);
            }
        }
        return index;
    }

    @Override
    public void search() {
        int[] result = new int[N];
        result[0] = 0;
        visited[0] = true;
        dfs(result, 1, 0);
        
        System.out.println("[DFS]");
        System.out.println(Arrays.toString(result));
    }
    
}

 

 

3. DFS의 시간 복잡도

 

DFS 는 그래프의 모든 정점, 간선을 조회한다.

그래프의 정점의 개수를 V, 간선의 개수를 E라고 할 때 DFS의 시간 복잡도는 O(V + E)가 된다.

 

 

[reference]

- https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

Depth First Search or DFS for a Graph - GeeksforGeeks