[자료구조] DFS & BFS

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다.

 

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

 

DFS는 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그림에서와 같이 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문하는 식으로 탐색한다. DFS는 스택(Stack) 자료구조를 이용한다.

 

DFS의 특징

• 모든 노드를 방문하고자 할 때 사용되는 방법이다.
• DFS는 BFS(너비 우선 탐색)에 비해 비교적 간단하다.
• 검색 속도는 DFS가 BFS에 비해 느리다.
• 스택이나 재귀함수를 이용하여 구현한다.

 

코드 구현

import java.util.*;

class Graph {
    private int vertices; // 정점의 개수
    private LinkedList<Integer>[] adjList; // 인접 리스트

    // 그래프 생성자
    Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 그래프에 간선 추가
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // DFS 알고리즘 (재귀적 방식)
    void DFSUtil(int v, boolean[] visited) {
        // 현재 노드를 방문 처리
        visited[v] = true;
        System.out.print(v + " ");

        // 인접한 모든 정점들을 재귀적으로 방문
        for (int n : adjList[v]) {
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }

    // DFS 호출 함수
    void DFS(int v) {
        boolean[] visited = new boolean[vertices]; // 방문 여부 저장 배열
        DFSUtil(v, visited);
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("DFS 시작 (정점 2부터):");
        g.DFS(2);
    }
}

---

너비 우선 탐색(BFS, Breadth-First Search)

 

BFS는 너비 우선 탐색이라고도 부르며, 그래프와 트리의 가까운 노드부터 탐색하는 알고리즘이다. 그림에서와 같이 루트 노드와 같은 거리에 있는 노드를 우선으로 방문하며 탐색한다. BFS는 큐(Queue) 자료구조를 이용한다.

 

BFS의 특징

• 최단 경로를 찾고자 할 때 사용한다. (위의 그림과 같이 BFS는 수평으로 탐색하는 방법이기 때문에 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있다.)
• 예를 들어 A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있다.
• 큐를 이용하여 구현한다.

 

코드 구현

import java.util.*;

class Graph {
    private int vertices; // 정점의 개수
    private LinkedList<Integer>[] adjList; // 인접 리스트

    // 그래프 생성자
    Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 그래프에 간선 추가
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // BFS 알고리즘
    void BFS(int s) {
        boolean[] visited = new boolean[vertices]; // 방문 여부 저장 배열
        LinkedList<Integer> queue = new LinkedList<>();

        // 시작 노드를 방문 처리하고 큐에 삽입
        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()) {
            // 큐에서 정점을 하나 꺼내서 출력
            s = queue.poll();
            System.out.print(s + " ");

            // 인접한 모든 정점들을 큐에 삽입 (방문하지 않은 경우)
            for (int n : adjList[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("BFS 시작 (정점 2부터):");
        g.BFS(2);
    }
}

 

DFS와 BFS의 시간 복잡도

DFS

• 시간 복잡도 (인접 리스트): O(V+E)
• 시간 복잡도 (인접 행렬): O(V²)
• 공간 복잡도: O(V)

BFS

• 시간 복잡도 (인접 리스트): O(V+E)
• 시간 복잡도 (인접 행렬): O(V²)
• 공간 복잡도: O(V)