7 min to read

BFS 와 DFS

BFS 와 DFS 에 대해 알아봅니다.

Thinking

트리(Tree) 를 순회하는 방법은 3 가지로 나뉩니다.

트리의 Node 들은 계층이 정해져 있어 visited 배열이 없어도 충분히 순회가 가능합니다.

애초에 트리(Tree) 는 노드의 개수가 N 개이면, (N - 1) 개의 간선들로 이뤄지고, 순환이란 것 자체가 없어야 합니다.

그렇지만 그래프의 정점들은 계층이 따로 정해진 것도 아니기 때문에 어느 지점에서 시작을 하든 순회 결과 값은 달라질 수 있습니다.

(물론 정점들의 가중치 순서를 기준으로 ASC 를 하는 것이 관례이긴 합니다.)

그래서 이번 문서에서는 그래프의 탐색 방법인 DFS 와 BFS 를 다뤄보도록 하겠습니다.

Adjacency Matrix vs List

그래프 탐색 알고리즘을 공부하기 앞서 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List) 둘 중 하나를 선택해야 하는 경우가 있습니다.

인접 행렬을 사용하는 경우

인접 리스트를 사용하는 경우

DFS

소스 코드는 다음과 같습니다.

재귀 함수를 사용하는 방법

import java.util.Arrays;
import java.util.List;

public class DFS_Recursive {
    static final int N = 7;
    static final int S = 1;

    static List<Integer>[] graph = new List[] {
        null,
        Arrays.asList(2, 5),
        Arrays.asList(1, 4, 7),
        Arrays.asList(5, 6, 7),
        Arrays.asList(2, 7),
        Arrays.asList(1, 3),
        Arrays.asList(3, 7),
        Arrays.asList(2, 3, 4, 6)
    };

    static boolean[] visited;
    static StringBuilder sb;

    static void dfs_recursive(int vtx){
        visited[vtx] = true;
        sb.append(String.format("%d ", vtx));
        for(int next : graph[vtx]){
            if(!visited[next]){
                dfs_recursive(next);
            }
        }
    }

    static void initialize(){
        visited = new boolean[N + 1];
        sb = new StringBuilder();
    }

    public static void main(String[] args){
        initialize();
        dfs_recursive(S);
        System.out.println(sb.toString());
    }
}

Stack 자료구조를 사용하는 방법

DFS 의 순서를 올바르게 얻기 위해 인접 리스트 순서를 거꾸로 작성해야 합니다.

그래서 Stack 자료구조로 DFS 를 구현하는 것을 비추천 하는 것입니다.

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class DFS_Stack {
    static final int N = 7;
    static final int S = 1;

    static List<Integer>[] graph = new List[] {
        null,
        Arrays.asList(5, 2),
        Arrays.asList(7, 4, 1),
        Arrays.asList(7, 6, 5),
        Arrays.asList(7, 2),
        Arrays.asList(3, 1),
        Arrays.asList(7, 3),
        Arrays.asList(6, 4, 3, 2)
    };

    static void dfs_stack(){
        boolean[] visited = new boolean[N + 1];

        Stack<Integer> stack = new Stack<>();
        stack.push(S);

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            int cur = stack.pop();
            if(!visited[cur]) {
                sb.append(String.format("%d ", cur));
                visited[cur] = true;
                for (int next : graph[cur]) {
                    if (!visited[next]) {
                        stack.push(next);
                    }
                }
            }
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args){
        dfs_stack();
    }
}

BFS

소스 코드는 다음과 같습니다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {
    static final int N = 7;
    static final int S = 1;

    static List<Integer>[] graph = new List[] {
        null,
        Arrays.asList(2, 5),
        Arrays.asList(1, 4, 7),
        Arrays.asList(5, 6, 7),
        Arrays.asList(2, 7),
        Arrays.asList(1, 3),
        Arrays.asList(3, 7),
        Arrays.asList(2, 3, 4, 6)
    };

    static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];

        queue.offer(S);
        visited[S] = true;

        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            int cur = queue.poll();
            sb.append(String.format("%d ", cur));
            for(int next : graph[cur]) {
                if(!visited[next]){
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args){
        bfs();
    }
}