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

개요

깊이우선탐색은 대표적인 그래프 탐색 알고리즘이다.

 

직접 그린 그림

위와 같은 그래프를 탐색하고자 한다.

간선으로 연결된 노드를 더 이상 간선이 연결되지 않을 때 까지 탐색하는 방법을 깊이 우선 탐색이라 한다.

간선으로 연결된 모든 노드를 우선으로 탐색하고, 더 이상 해당 노드에 연결된 간선이 없을 경우 하위 노드에서 같은 방식으로 연결된 모든 노드를 탐색하는 것을 너비 우선 탐색이라고 한다.

 

너비 우선 탐색은 다음 글에서 살펴보기로 하고, 이번 글에서는 DFS 에 대해 자세히 알아보자.

 

DFS (Depth First Search)

1.1 설명

직접 그린 그림

 

 

1번 노드에서 시작한다.

연결된 간선이 있으니, 2번 노드부터 탐색한다.

 

 

 

 

 

 

 

 

2번 노드로 이동했다.

간선으로 연결된 3번 노드로 이동한다.

 

 

 

 

 

 

 

 

3번 노드로 이동했다.

간선으로 연결된 4번 노드로 이동한다.

 

 

 

 

 

 

 

 

 

 

4번 노드로 이동했다.

간선으로 연결된 5번 노드로 이동한다.

 

 

 

 

 

 

 

 

 

 

 

모든 노드를 탐색 완료했다.

 

 

 

 

 

 

 

 

 

 

위에서 깊이를 우선으로 탐색을 이어나가는 과정을 살펴보았다.

이제 되돌아오면서, 탐색하지 않은 다른 노드가 있는지 검사해야 한다.

깊이를 우선으로 탐색하기 때문에, 더 깊은 위치에 있는 노드를 우선 탐색해야함을 잊지 말자.

 

 

5번 노드까지 탐색 완료 후, 더 이상 간선으로 연결된 노드가 없다면 이전 노드인 4번 노드로 복귀한다.

4번 노드로 돌아와서, 간선으로 연결된 다른 노드가 있는지 검사한다.

 

 

 

 

 

 

 

 

간선으로 연결된 노드가 없다면, 이전 노드인 3번 노드로 이동한다.

 

 

 

 

 

 

 

 

 

간선으로 연결된 노드가 없다면, 이전 노드인 2번 노드로 이동한다.

 

 

 

 

 

 

 

 

 

 

간선으로 연결된 노드가 없다면, 이전 노드인 1번 노드로 이동한다.

 

 

 

 

 

 

 

 

 

이전 노드로 복귀한 후, 추가로 탐색해야 할 노드가 있는지 검사하게 된다. 위의 예제에서는 추가로 연결된 간선이 없어서 1번 노드까지 되돌아왔다.

 

따라서 그래프를 깊이우선탐색 한 최종 탐색 순서는 1 -> 2 -> 3 -> 4 -> 5 가 된다.

만약 돌아오는 과정 중에 추가로 연결된 노드가 있었다면 어떻게 될까?

 

 

3번 노드로 복귀하고 보니, 간선으로 연결된 6번 노드가 존재한다.

따라서 2번 노드로 복귀하는 것이 아니라, 6번 노드로 깊이우선탐색을 진행한다.

 

 

 

 

 

 

 

 

 

 

 

 

6번 노드를 우선 탐색하였다.

 

 

 

 

 

 

 

 

 

 

 

 

 

이 경우의 그래프 탐색 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 이 된다.

이제 좀 더 복잡한 그래프로 학습한 내용을 확인해보자.

 

직접 그린 그림

 

 

1.2 구현

DFS 는 보통 스택을 사용하여 구현한다. 

스택의 구현은 Stack 자료구조를 직접 사용하지 않고 함수의 재귀호출을 이용하기도 하는데, Java compiler 가 반복되는 함수의 호출을 스택 구조로 쌓아두고, 제어권을 inner 함수로 넘기기 때문이다.

 

직접 그린 그림

먼저 그래프를 코드로 표현해보자.

 

직접 그린 그림

그래프 탐색 알고리즘을 구현하는데 있어서 코드 상으로 집중해야 하는 것은 그래프 탐색 순서이다. 노드의 표현 방식은 경우에 따라서 유연하게 대처해도 무방하다.

 

먼저 생각해봐야 할 부분은 간선을 코드로 나타내는 방법이다.

크게 2가지 방법이 있다. 

 

1.2.1 인접 행렬 방식

인접 행렬 방식으로 노드와 노드를 연결한 간선을 표현해보자.

 

직접 그린 그림

 

2차원 배열로 표현한다.

a 노드와 b 노드가 간선으로 연결되어 있는 경우 해당 위치에 1 을 저장해둔다.

 

Array[a노드][b노드] = 1

 

반대로 간선으로 연결되어 있지 않은 노드의 경우는 0 으로 표현한다.

 

Array[b노드][c노드] = 0

 

이제 코드로 구현해보자.

 

class Graph {

    private int vertexCount;
    private int[][] graphs;
    private boolean[] visits;

    public Graph(int vertexCount) { ... }

    public void connect(int start, int end) { ... }

    public void dfs(int vertex) { ... }
}

 

먼저 interface 를 살펴보면, Graph 클래스는 노드의 개수(vertexCount), 그래프 행렬(graphs) 그리고 방문 체크를 할 수 있는 visits 를 속성으로 가지고 있다.

 

함수를 보자.

 

public Graph(int vertexCount) {}

생성자 함수이다. 노드의 총 개수를 인자로 받아 그래프 행렬와 방문 체크 배열을 초기화 시키는 역할을 한다.

 

public void connect(int start, int end) {}

시작 노드와 종료 노드를 받아 둘을 연결시키는 함수이다.

 

public void dfs(int vertext) {}

DFS 로 그래프 탐색을 시작하는 함수이다. 이 함수는 재귀호출하여 그래프를 탐색한다.

 

위의 인터페이스는 잠시 후 언급할 DFS 의 또다른 구현 방법인 인접 리스트 방식에서도 동일하게 사용된다.

잘 알아두도록 하자.

 

위에서 학습한 깊이우선탐색 방식의 그래프 탐색 순서를 dfs 함수로 구현해보자.

 

public void dfs(int vertex) {
    visits[vertex] = true;                // 방문 체크 배열에 해당 노드 방문 기록
    System.out.print(vertex + " ");       // 방문한 노드 출력
    
    for (int i = 0; i < vertexCount; i++) {
        // 방문하지 않았고, 연결된 간선을 방문
        if (!visits[i] && graphs[vertex][i] == 1) {    
          dfs(i);
        }
    }
}

 

 

완성된 코드를 보면 생각보다 단순하다.

그래프의 탐색 순서를 표현하기 위해 방문 후에 바로 노드의 위치를 출력해준다.

 

graphs[vertex] 는 vertex 노드에 간선으로 연결된 모든 노드의 기록을 가지고 있다.

만약 graphs[vertex][3] = 1 이라면, vertex 노드는 3번 노드에 연결되어 있다는 의미이다.

 

따라서 방문하지 않았고, graphs[vertex][i] == 1 인 노드를 dfs 함수로 재귀호출 해준다.

 

1.2.2 인접 리스트 방식

이번에는 인접 리스트 방식으로 노드와 노드를 연결한 간선을 표현해보자.

 

1차원 배열에 리스트가 연결된 형태로 표현한다.

인접 배열 방식과는 다르게 리스트에 들어가는 원소는 연결된 노드의 값이다.

 

인접 배열 방식보다 더욱 직관적이기 때문에 이해하기가 좀 더 쉽다.

 

바로 코드로 구현해보자.

 

class Graph {

    private int vertexCount;
    private List<LinkedList<Integer>> graphs;
    private boolean[] visits;

    public Graph(int vertexCount) { ... }

    public void connect(int start, int end) { ... }

    public void dfs(int vertex) { ... }
}

 

인접 배열 방식과 비교하여 달라진 점은 그래프의 표현 방식 뿐이다.

그 외 인터페이스는 동일하다.

 

dfs 함수의 구현은 어떻게 달라지는지 확인해보자.

 

public void dfs(int vertex) {
    visits[vertex] = true;                // 방문 체크 배열에 해당 노드 방문 기록
    System.out.print(vertex + " ");       // 방문한 노드 출력
    
    for (int i : graphs.get(vertex)) {
        // 방문하지 않은 노드를 방문
        if (!visits[i]) {    
          dfs(i);
        }
    }
}

 

for (int i : graphs.get(vertex)) {}

위 반복문은 LinkedList<Integer> 타입의 원소를 하나씩 반환한다. 

따라서 변수 i 는 노드의 값이다.

 

Code

이제 전체 소스코드를 확인해보자.

 

1. 인접 배열 방식

public class AdjacentMatrixDFS {

    private int vertexCount;
    private int[][] graphs;
    private boolean[] visits;

    public AdjacentMatrixDFS(int vertexCount) {
        this.vertexCount = vertexCount;
        this.graphs = new int[vertexCount][vertexCount];
        this.visits = new boolean[vertexCount];
    }

    public void edge(int start, int end) {
        graphs[start][end] = 1;
        graphs[end][start] = 1;
    }

    public void dfs(int vertex) {
        visits[vertex] = true;
        System.out.print(vertex + " ");

        for (int i = 0; i < vertexCount; i++) {
            if (!visits[i] && graphs[vertex][i] == 1) {
                dfs(i);
            }
        }
    }

    public void print() {
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                System.out.print(graphs[i][j] + " ");
            }
            System.out.println(" ");
        }
    }

    public static void main(String[] args) {
        AdjacentMatrixDFS adjacentMatrixDFS = new AdjacentMatrixDFS(10);

        adjacentMatrixDFS.edge(0, 1);
        adjacentMatrixDFS.edge(0, 2);
        adjacentMatrixDFS.edge(1, 3);
        adjacentMatrixDFS.edge(1, 4);
        adjacentMatrixDFS.edge(2, 5);
        adjacentMatrixDFS.edge(2, 6);
        adjacentMatrixDFS.edge(3, 7);
        adjacentMatrixDFS.edge(4, 7);
        adjacentMatrixDFS.edge(5, 7);
        adjacentMatrixDFS.edge(6, 7);

        adjacentMatrixDFS.print();
        adjacentMatrixDFS.dfs(0);
    }
}

 

2. 인접 리스트 방식

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;

public class AdjacentListDFS {

    private int vertexCount;
    private ArrayList<LinkedList<Integer>> graphs;
    private boolean[] visits;

    public AdjacentListDFS(int vertexCount) {
        this.vertexCount = vertexCount;
        this.graphs = new ArrayList<LinkedList<Integer>>();

        for (int i = 0; i < vertexCount; i++) {
            this.graphs.add(new LinkedList<Integer>());
        }

        this.visits = new boolean[vertexCount];
    }

    public void edge(int start, int end) {
        graphs.get(start).add(end);
        graphs.get(end).add(start);
    }

    public void dfs(int vertex) {
        visits[vertex] = true;
        System.out.print(vertex + " ");

        for (int i : graphs.get(vertex)) {
            if (!visits[i]) {
                dfs(i);
            }
        }
    }

    public void print() {
        for (int i = 0; i < vertexCount; i++) {
            System.out.print(i + " ");

            ListIterator iterator = graphs.get(i).listIterator(0);
            
            while (iterator.hasNext()) {
                int next = (int) iterator.next();
                System.out.print(next + " ");
            }

            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacentListDFS adjacentListDFS = new AdjacentListDFS(8);

        adjacentListDFS.edge(0, 1);
        adjacentListDFS.edge(0, 2);
        adjacentListDFS.edge(1, 3);
        adjacentListDFS.edge(1, 4);
        adjacentListDFS.edge(2, 5);
        adjacentListDFS.edge(2, 6);
        adjacentListDFS.edge(3, 7);
        adjacentListDFS.edge(4, 7);
        adjacentListDFS.edge(5, 7);
        adjacentListDFS.edge(6, 7);

        adjacentListDFS.print();
        adjacentListDFS.dfs(0);
    }
}