---
title: "BFS: 같은 거리 layer를 큐로 보존하는 Java 최단 경로 탐색"
slug: "java-bfs"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","BFS","Graph","Shortest Path","Queue"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "무가중 그래프에서 발견 시점 방문 처리와 FIFO layer 불변식이 최소 hop을 보장하는 이유를 증명하고, primitive queue·거리·부모 배열의 메모리를 분석한다."
kind: "Deep Dive"
evidence: "Princeton Algorithms 4/e undirected graph/BreadthFirstPaths 자료·Java SE 21 ArrayDeque/JVMS 21을 대조하고 BfsDemo를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

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의 탐색 일부다.

| dequeue | queue before | 새로 발견 | 거리/부모 | queue after |
| ---: | --- | --- | --- | --- |
| 0 | `[0]` | 1, 2 | `d=1,p=0` | `[1,2]` |
| 1 | `[1,2]` | 3 | `d=2,p=1` | `[2,3]` |
| 2 | `[2,3]` | 없음(3은 이미 발견) | 유지 | `[3]` |
| 3 | `[3]` | 4 | `d=3,p=3` | `[4]` |

정점을 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 프로그램이다.

```java
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)));
    }
}
```

```bash
javac --release 21 BfsDemo.java
java BfsDemo
```

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

```text
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와 비교

| 목표 | 선택 | 이유 |
| --- | --- | --- |
| 무가중 최소 hop | BFS | layer 첫 발견이 최소 |
| 연결 여부/깊은 경로 | BFS 또는 DFS | memory shape가 폭/깊이로 다름 |
| 비음수 가중 최소합 | Dijkstra | priority distance 필요 |
| 단일 source-target, 큰 무가중 graph | 양방향 BFS 검토 | 양쪽 frontier가 만날 때 탐색 공간 감소 가능 |

양방향 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](https://algs4.cs.princeton.edu/41graph/)
- Robert Sedgewick, Kevin Wayne, [BreadthFirstPaths.java](https://algs4.cs.princeton.edu/41graph/BreadthFirstPaths.java.html)
- Oracle, [ArrayDeque — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayDeque.html)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Runtime Data Areas](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)