BFS와 DFS

그래프란?

그래프란 다대다 연결관계를 표현할 수 있는, 여러 노드와 간선으로 연결된 자료구조를 의미합니다.

그래프는 여러 개의 정점(Vertex) 와 간선(Edge)로 이루어져 있습니다. G=(V,E) 로 표기합니다.

• 정점(Vertex): 그래프의 구성요소
• 간선(Edge): 두 정점을 연결하는 선
• 차수(Degree): 정점 하나에 연결된 간선의 수

그래프 탐색

그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 방문하는 것을 의미합니다.

그래프 탐색에는 크게 두 가지 방법이 있습니다.

(1) BFS_너비우선탐색

BFS는 Breadth-First-Search의 약자로 너비 우선 탐색을 의미합니다. 너비 우선 탐색은 기준 노드에서 인접한 노드를 먼저 탐색하는 방법인데요. 시작 정점으로부터 가까운 정점부터 방문하는 것입니다.

즉, 이름에서도 알 수 있듯이 깊게 탐색하는 것이 아닌 넓게 탐색하는 것이죠!

(2) DFS_깊이우선탐색

DFS는 Depth-First-Search의 약자로 깊이 우선 탐색을 의미합니다. 깊이 우선 탐색은 기준 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다.

즉, 이름에서도 알 수 있듯이 넓게 탐색하는 것이 아닌 깊게 탐색하는 것이죠!

(3) 비교

그래프 탐색 구현 (Java)

예시는 아래왁 같은 그림의 그래프를 탐색하는 코드입니다.

(1) BFS 코드

BFS는 자료구조 중 큐(Queue)를 사용해서 구현합니다.

import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int[][] graph = {
        {}, {2,3}, {4,5}, {6,7,8}, {}, {9}, {}, {10}, {}, {}, {}
        };
    static boolean[] visited; // 방문 확인용 배열

    public static void main(String[] args) {
        // V는 10개지만 배열의 인덱스를 사용하기 위해 V+1의 공간을 만들어줍니다.
        visited = new boolean[10+1];  

        System.out.println("BFS 출력 결과");
        bfs(1); // 출력 결과: 1 2 3 4 5 6 7 8 9 10 
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()) {
            int v = queue.poll();
            if(!visited[v]) {
                visited[v] = true; // 방문 체크
                System.out.print(v + " ");

                for(int next: graph[v]) {
                    queue.add(next);
                }
            }
        }
    }
}

(2) DFS 코드

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 가집니다. 아래 코드는 재귀 호출을 통해 구현한 DFS입니다.

public class Main {
    static int[][] graph = {
        {}, {2,3}, {4,5}, {6,7,8}, {}, {9}, {}, {10}, {}, {}, {}
        };
    static boolean[] visited; // 방문 확인용 배열
    public static void main(String[] args) {
        // V는 10개지만 배열의 인덱스를 사용하기 위해 V+1의 공간을 만들어줍니다.
        visited = new boolean[10+1];  

        System.out.println("DFS 출력 결과");
        dfs(1); // 출력 결과: 1 2 4 5 9 3 6 7 10 8
    }

    static void dfs(int v) {
        if(!visited[v]) {
            visited[v] = true;
            System.out.print(v + " ");

            for(int next: graph[v]) {
                dfs(next); // 재귀
            }
        }
    }
}