Java로 구현하는 BFS와 DFS: 그래프 탐색 알고리즘 비교

이 글에서는 두 가지 주요 그래프 탐색 알고리즘인 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)을 Java로 구현하는 방법을 알아본다.

그래프 구현

먼저, 우리의 알고리즘들이 작동할 그래프 구조를 정의해보자.
다음은 인접 리스트를 사용한 간단하면서도 유연한 그래프 클래스다.

import java.util.*;

public class Graph<T> {
    private Map<T, List<T>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addVertex(T vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(T source, T destination) {
        adjacencyList.get(source).add(destination);
        // 무방향 그래프의 경우 아래 라인 추가
        // adjacencyList.get(destination).add(source);
    }

    public List<T> getNeighbors(T vertex) {
        return adjacencyList.get(vertex);
    }

    public Set<T> getVertices() {
        return adjacencyList.keySet();
    }
}

이 그래프 클래스는 제네릭을 사용하여 다양한 타입의 정점을 지원한다. 정점 추가, 간선 추가, 이웃 정점 조회 등의 기본적인 작업을 수행할 수 있다.

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

BFS는 시작 정점으로부터 가까운 정점을 먼저 방문하고, 점차 멀리 있는 정점을 방문하는 알고리즘이다.
큐를 사용하여 구현된다.

import java.util.*;

public class BFS<T> {
    public List<T> bfs(Graph<T> graph, T start) {
        List<T> visited = new ArrayList<>();
        Queue<T> queue = new LinkedList<>();
        Set<T> enqueued = new HashSet<>();

        queue.offer(start);
        enqueued.add(start);

        while (!queue.isEmpty()) {
            T vertex = queue.poll();
            visited.add(vertex);

            for (T neighbor : graph.getNeighbors(vertex)) {
                if (!enqueued.contains(neighbor)) {
                    queue.offer(neighbor);
                    enqueued.add(neighbor);
                }
            }
        }

        return visited;
    }
}

이 BFS 구현은 시작 정점에서 시작하여 그래프를 너비 우선으로 탐색하고, 방문한 정점들의 리스트를 반환한다.
enqueued 집합은 이미 큐에 추가된 정점을 추적하여 중복 방문을 방지한다.

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

DFS는 가능한 한 깊이 들어가면서 그래프를 탐색하고, 더 이상 탐색할 수 없을 때 백트래킹하는 알고리즘이다.
DFS는 스택을 사용하거나 재귀적으로 구현할 수 있다.

스택 기반 DFS

import java.util.*;

public class DFS<T> {
    public List<T> dfsIterative(Graph<T> graph, T start) {
        List<T> visited = new ArrayList<>();
        Stack<T> stack = new Stack<>();
        Set<T> discovered = new HashSet<>();

        stack.push(start);
        discovered.add(start);

        while (!stack.isEmpty()) {
            T vertex = stack.pop();
            visited.add(vertex);

            for (T neighbor : graph.getNeighbors(vertex)) {
                if (!discovered.contains(neighbor)) {
                    stack.push(neighbor);
                    discovered.add(neighbor);
                }
            }
        }

        return visited;
    }
}

이 구현은 명시적인 스택을 사용하여 DFS를 수행한다.
discovered 집합은 이미 발견된 정점을 추적하여 중복 방문을 방지한다.

재귀 기반 DFS

import java.util.*;

public class DFS<T> {
    public List<T> dfsRecursive(Graph<T> graph, T start) {
        List<T> visited = new ArrayList<>();
        Set<T> discovered = new HashSet<>();
        dfsRecursiveHelper(graph, start, visited, discovered);
        return visited;
    }

    private void dfsRecursiveHelper(Graph<T> graph, T vertex, List<T> visited, Set<T> discovered) {
        discovered.add(vertex);
        visited.add(vertex);

        for (T neighbor : graph.getNeighbors(vertex)) {
            if (!discovered.contains(neighbor)) {
                dfsRecursiveHelper(graph, neighbor, visited, discovered);
            }
        }
    }
}

이 구현은 재귀를 사용하여 DFS를 수행한다.
시스템 스택을 암묵적으로 사용하며, 코드가 더 간결하고 직관적일 수 있다.

사용 예시

다음은 위에서 구현한 BFS와 DFS를 사용하는 예시다.

public class Main {
    public static void main(String[] args) {
        Graph<Integer> graph = new Graph<>();
        for (int i = 0; i < 6; i++) {
            graph.addVertex(i);
        }
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);

        BFS<Integer> bfs = new BFS<>();
        System.out.println("BFS traversal: " + bfs.bfs(graph, 0));

        DFS<Integer> dfs = new DFS<>();
        System.out.println("DFS traversal (iterative): " + dfs.dfsIterative(graph, 0));
        System.out.println("DFS traversal (recursive): " + dfs.dfsRecursive(graph, 0));
    }
}

BFS와 DFS 비교

탐색 순서:
- BFS: 너비 우선으로 탐색한다. 시작 정점에서 가까운 정점부터 방문한다.
- DFS: 깊이 우선으로 탐색한다. 한 경로를 끝까지 탐색한 후 백트래킹한다.
메모리 사용:
- BFS: 큐를 사용하므로, 너비가 넓은 그래프에서는 많은 메모리를 사용할 수 있다.
- DFS (스택): 명시적 스택을 사용하며, 깊이가 깊은 그래프에서도 메모리 사용을 제어할 수 있다.
- DFS (재귀): 시스템 스택을 사용하므로, 매우 깊은 그래프에서는 스택 오버플로우가 발생할 수 있다.
최단 경로:
- BFS: 가중치 없는 그래프에서 항상 최단 경로를 찾는다.
- DFS: 최단 경로를 보장하지 않는다.
구현 방식:
- BFS: 주로 큐를 사용하여 구현한다.
- DFS: 명시적 스택 또는 재귀를 사용하여 구현할 수 있다.
응용:
- BFS: 최단 경로 문제, 네트워크 브로드캐스트, 가비지 컬렉션, 웹 크롤링 등에 사용된다.
- DFS: 위상 정렬, 사이클 검출, 미로 생성, 강한 연결 요소 찾기 등에 사용된다.
시간 복잡도: BFS와 DFS 모두 모든 정점과 간선을 한 번씩 방문하므로, 시간 복잡도는 동일하다:
- 인접 리스트를 사용할 경우: O(V + E), 여기서 V는 정점의 수, E는 간선의 수다.
- 인접 행렬을 사용할 경우: O(V^2)
특징:
- BFS: 레벨 순서 탐색을 제공한다. 같은 레벨의 모든 노드를 탐색한 후 다음 레벨로 이동한다.
- DFS: 백트래킹을 통해 모든 가능한 경로를 탐색할 수 있다.

결론

BFS와 DFS는 각각 장단점이 있으며, 문제의 특성에 따라 적절한 알고리즘을 선택해야 한다.
BFS는 최단 경로 문제에, DFS는 그래프의 연결성이나 위상 정렬 같은 문제에 주로 사용된다.
DFS의 경우 스택 기반과 재귀 기반 구현 중 상황에 따라 적절한 방식을 선택할 수 있다.