그래프 탐색 알고리즘 (1) DFS 를 중심으로

1. 들어가기

그래프에 표시된 모든 노드를 탐색하는 방법으로는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적이다. 이때, 효율적인 탐색 방법으로는 깊이 우선 탐색(DFS;Depth First Search)과 너비 우선 탐색(BFS;Breadth First Search)이 대표적이다. 필자는 이번 글에서 깊이 우선 탐색 알고리즘을 중심으로 다뤄볼 것이다.
 

2. 깊이 우선 탐색

그래프 정점(꼭짓점)이 1, 2, 3, 4, ... , N 개가 있다고 하자. 깊이 우선 탐색은 시작점을 1 이라고 할 때, 1 에서 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 2에 방문하고, 꼭짓점 2에 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 3를 반복한다. 이때 인접한 모든 꼭짓점을 방문한 경우, 이전에 마지막으로 방문한 꼭짓점 N-1로 돌아가서 인접한 꼭짓점 중 방문하지 않은 꼭짓점을 다시 방문한다. 이 과정을 반복한다. 이때, 방문하지 않은 꼭짓점들을 방문하기 위해 이전의 꼭짓점에 방문하는 과정을 백 트래킹(Back Tracking)이라고 한다. 이와 관련해서는 다음 글에서 다루도록 하겠다.
 
깊이 우선 탐색에서 하나의 꼭짓점에 인접한 꼭짓점이 두 개 이상인 경우, 탐색 기준에 따라 탐색하는 순서가 달라질 수 있다.  다음 그림을 통해 살펴보도록 하자. 편의상 시작 정점을 A라고 가정하고, 그래프를 탐색해보겠다. 단, 사전적 순서를 먼저 탐색한다는 가정 하에 탐색한다.
 

그래프

(1) 시작 노드 A와 인접하고, 아직 탐색되지 않은 꼭짓점과 B가 있을 때, 사전적 순서가 더 빠른 B를 먼저 탐색한다.
      A - B
(2) B와 인접하고 탐색되지 않은 꼭짓점 D와 E가 있을 때, 사전적 순서가 더 빠른 D를 먼저 선택한다.
      A - B - D
(3) D와 인접하고 탐색되지 않은 꼭짓점이 없으므로, 다시 B로 백 트래킹하여 B와 인접하고 탐색되지 않은 꼭짓점 E를 탐색한다.
     A - B - D - E
(4) E와 인접하고 탐색되지 않은 꼭짓점 F와 C가 있다. 이때 사전적 순서가 더 빠른 C를 탐색한다.
    A - B - D - E - C
(5) C와 인접한 꼭짓점이 없으므로 E로 백 트래킹 하여 E와 인접하고 탐색되지 않은 꼭짓점 F를 탐색한다.
    A - B - D - E - C - F
(6) F와 인접하고 탐색되지 않은 G를 탐색한다.
    A - B - D - E - C - F - G
(7) G와 인접하고 탐색되지 않은 H를 탐색한다.
    A - B - D - E - C - F - G - H
(8) 모든 꼭짓점을 탐색했으므로 탐색을 종료한다.
 
깊이 우선 탐색 과정을 그래프로 나타내면 다음 그림과 같다.

DFS 탐색 경로를 나타낸 그래프

 

3. 정리

깊이 우선 탐색 과정을 정리하면 다음과 같다.
1) 시작점 n을 탐색
2) 정점에 인접한 꼭짓점 들 중 탐색하지 않은 n에 인접한 꼭짓점을 탐색
3) n에 인접한 꼭짓점에 방문하면, 그 꼭짓점을 시작점 n으로 하여 2)를 반복
4) 모든 꼭짓점이 탐색됐으면, 이전에 탐색한 꼭짓점을 n으로 하여 2), 3)을 반복
5) 그래프의 모든 꼭짓점을 탐색할 때까지 반복
 

4. 구현

public class Main {
    static int[][] graph;
    static boolean[] visited;
    static int N, M; // N=꼭짓점 수, M=간선 수
    static StringBuffer sb;
    public static void dfs(int v){
        visited[v] = true;
        sb.append(Character.toString(v+65) + " ");
        for(int i=1; i<=N; i++){
            if(!visited[i]){
                if(graph[v][i] == 1)
                    dfs(i);
            }
        }
    }

    public static void main(String[] args){
        char[] p1 = new char[]{'A', 'A', 'B', 'B', 'C', 'E', 'F', 'G'};
        char[] p2 = new char[]{'B', 'C', 'D', 'E', 'E', 'F', 'G', 'H'};

        N = 8;
        M = 8;

        visited = new boolean[N+1];
        graph = new int[N+1][N+1];
        sb = new StringBuffer();

        for(int i=0; i<M; i++){
            int a = Character.valueOf(p1[i]) - 65;
            int b = Character.valueOf(p2[i]) - 65;

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        dfs(0);
        System.out.println(new String(sb)); // A B D E C F G H 
    }
}

 

5. DFS 구현 시 고려해야 할 사항

- 재귀로 인한 시간복잡도 이슈
DFS로 탐색하는 경우 특정한 조건문을 추가하여야 한다. 그래야 재귀의 반복 횟수를 줄일 수 있다. 백 트래킹이 이뤄지는 시점의 조건을 반드시 추가하여 방문이 필요없는 구간을 다시 방문하지 않도록 한다. visited 배열을 사용하는 것도 백 트래킹을 하게 하는 한 예다. 
 
참고문헌 : 컴퓨팅 사고력을 키우는 이산수학 / 한빛아카데미