BFS: 같은 거리 layer를 큐로 보존하는 Java 최단 경로 탐색

BFS는 가까운 정점부터 방문한다. 정확히는 source에서 edge 수가 $d$인 모든 정점을 $d+1$인 정점보다 먼저 queue에서 꺼낸다. 이 layer 순서 때문에 모든 edge 비용이 동일한 그래프의 최소 hop을 보장한다.

1. 문제 계약과 그래프 표현

입력은 정점 0..V-1의 인접 배열 int[][] graph와 source다. 결과는 source부터 각 정점까지 최소 edge 수 distance, 실제 경로 복원을 위한 parent다. 도달 불가능하면 distance -1, path는 빈 배열이다. 잘못된 source, null adjacency, 범위 밖 edge는 계약 위반이다.

예제 그래프는 무방향이므로 양쪽 adjacency를 모두 넣었다. 일반 구현은 입력이 대칭인지 자동 보장하지 않는다. directed graph에서도 BFS는 동작하지만 edge 방향을 그대로 따른다.

2. 발견 시점에 방문 표시해야 한다

source 0의 탐색 일부다.

정점을 queue에 넣는 발견 시점에 distance를 기록한다. dequeue 때까지 미루면 여러 부모가 같은 정점을 중복 enqueue해 queue와 메모리가 불필요하게 커진다.

3. layer 불변식과 최소 거리 증명

불변식: queue의 정점은 distance가 감소하지 않는 순서로 들어 있고, 발견된 정점의 distance는 source에서 그 정점까지 알려진 최소 edge 수다.

source 거리는 0으로 맞다. 거리 $d$인 정점을 꺼내 처음 보는 neighbor에 $d+1$을 부여한다. FIFO 때문에 거리 $d$ 정점들이 먼저 처리되므로 그 neighbor보다 짧은 경로가 있었다면 더 이른 layer에서 이미 발견됐어야 한다. 따라서 첫 발견 거리가 최소다. parent는 그 최소 거리 경로의 직전 정점을 기록한다.

모든 edge weight가 1이라는 전제가 깨지면 “edge 수가 적다”와 “weight 합이 작다”가 달라진다. 예를 들어 직접 edge weight 100과 두 edge weight 1+1이 있으면 BFS는 직접 edge를 고르지만 비용 최단은 후자다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.Arrays;

public final class BfsDemo {
    record Result(int[] distance, int[] parent) {
        int[] pathTo(int target) {
            if (target < 0 || target >= distance.length) throw new IllegalArgumentException("invalid target");
            if (distance[target] == -1) return new int[0];
            int[] path = new int[distance[target] + 1];
            for (int at = target, i = path.length - 1; at != -1; at = parent[at]) path[i--] = at;
            return path;
        }
    }

    static Result bfs(int[][] graph, int source) {
        validate(graph, source);
        int[] distance = new int[graph.length];
        int[] parent = new int[graph.length];
        Arrays.fill(distance, -1);
        Arrays.fill(parent, -1);
        int[] queue = new int[graph.length];
        int head = 0, tail = 0;
        distance[source] = 0;
        queue[tail++] = source;
        while (head < tail) {
            int current = queue[head++];
            for (int next : graph[current]) {
                if (next < 0 || next >= graph.length) throw new IllegalArgumentException("invalid edge");
                if (distance[next] != -1) continue;
                distance[next] = distance[current] + 1;
                parent[next] = current;
                queue[tail++] = next;
            }
        }
        return new Result(distance, parent);
    }

    static void validate(int[][] graph, int source) {
        if (graph == null) throw new IllegalArgumentException("graph must not be null");
        if (source < 0 || source >= graph.length) throw new IllegalArgumentException("invalid source");
        for (int[] edges : graph) if (edges == null) throw new IllegalArgumentException("adjacency must not be null");
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2, 4}, {3}, {}};
        Result result = bfs(graph, 0);
        check(result.distance()[4] == 3, "shortest hops");
        check(Arrays.equals(result.pathTo(4), new int[] {0, 1, 3, 4}), "path");
        check(result.distance()[5] == -1 && result.pathTo(5).length == 0, "unreachable");
        System.out.println("distance=" + Arrays.toString(result.distance()));
        System.out.println("path(4)=" + Arrays.toString(result.pathTo(4)));
    }
}

javac --release 21 BfsDemo.java
java BfsDemo

직접 실행한 출력은 다음과 같다.

distance=[0, 1, 1, 2, 3, -1]
path(4)=[0, 1, 3, 4]

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

4. primitive queue를 쓴 이유

Java ArrayDeque<Integer>는 읽기 쉬운 기본 선택이지만 vertex마다 Integer boxing과 reference array를 사용한다. 예제는 정점이 최대 한 번 enqueue된다는 사실을 이용해 int[V] queue와 head/tail index를 쓴다. allocation profile이 단순하고 capacity가 정확히 V다.

일반 graph API나 동적 탐색에서는 ArrayDeque가 더 유연하다. 두 구현의 알고리즘은 같고 자료 표현만 다르다. 미세 최적화는 실제 allocation/throughput이 병목일 때 선택한다.

5. 시간·공간 복잡도 유도

adjacency list에서 각 정점은 최대 한 번 발견되어 enqueue/dequeue되고, 방문한 정점의 각 adjacency entry를 한 번 본다. 따라서 시간은 $O(V+E)$다. 무방향 graph는 한 edge가 양쪽 list에 있어 entry가 $2E$지만 상수 2를 제거한 차수는 같다.

distance, parent, queue가 각각 길이 V인 primitive array라 보조 공간은 $O(V)$. graph 입력 자체의 adjacency 저장 $O(V+E)$는 별도다. 경로 반환은 길이 $L$인 새 int[L]를 만든다.

6. frontier 폭과 JVM 메모리

재귀 frame은 없고 탐색 상태는 heap primitive arrays에 있다. local head/tail/current는 frame local variable이다. 최악의 star graph에서 source의 모든 neighbor가 한 번에 queue에 들어가 frontier가 $V-1$까지 커진다. BFS의 memory 병목은 깊이가 아니라 폭이다.

object graph를 List<List<Integer>>로 표현하면 list objects, backing arrays, boxed vertices가 추가된다. Big-O는 같아도 실제 heap과 GC가 다르다. 큰 graph에서는 JOL 한 객체보다 JFR allocation와 heap histogram, peak frontier를 함께 본다.

7. DFS·Dijkstra·bidirectional BFS와 비교

양방향 BFS는 directed edge 처리와 교차 판정이 복잡하고 항상 이득인 것은 아니다. 목표가 하나이고 reverse traversal이 가능할 때 측정한다.

8. 실제 도메인 적용

서비스 dependency의 최소 hop 영향 범위, social graph degrees-of-separation, game map의 동일 비용 이동에 쓸 수 있다. 운영 지표는 visited vertices, scanned edges, peak frontier, unreachable ratio, query timeout이다. 외부 입력 graph는 정점/간선 상한을 두지 않으면 memory DoS가 된다. distributed graph에서는 network shuffle과 partition skew가 지배해 단일 JVM $O(V+E)$만으로 용량을 판단할 수 없다.

9. 이건 피한다

• 가중 graph에 BFS를 써서 비용 최단이라 부른다. 최소 hop만 보장한다. 비음수 weight는 Dijkstra 등으로 바꾼다.
• dequeue 때 방문 표시한다. 같은 정점이 여러 번 queue에 들어가 frontier와 메모리가 폭증한다. enqueue 시 표시한다.
• graph 저장 공간을 보조 공간에서 숨긴다. adjacency가 실제 memory 대부분일 수 있다. 입력과 탐색 state를 따로 산정한다.
• ArrayDeque에서 remove(0) 같은 list 연산을 흉내 낸다. FIFO head 연산을 제공하는 queue를 쓴다.
• 정점/간선 상한 없이 공개 API로 탐색한다. CPU/heap을 고갈시킨다. budget, timeout, visited limit을 둔다.

Reference

• Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Undirected Graphs
• Robert Sedgewick, Kevin Wayne, BreadthFirstPaths.java
• Oracle, ArrayDeque — Java SE 21 API
• Oracle, The Java Virtual Machine Specification, Java SE 21 — Runtime Data Areas