先來個原始版本的 BFS:

Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
boolean[] visited = new boolean[n];
visited[src] = true;

while (!queue.isEmpty()) {
    int u = queue.poll();

    // we need the distance here

    for (int v:g[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        queue.offer(v);
    }
}

如果想知道 destination 和 src 的距離是多少， 常見的作法是另外開一個 array 來存， 或著把 distance 也一起放入 queue 裡。 (假設 distance 跟 u 型態一致，否則就只好另外開一個 queue)

以下提供一個多年前在線上競賽中看到其他參賽者的寫法。 總共只需要增加四行，充分利用了 BFS 每次只會深入一層的特性。

Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
boolean[] visited = new boolean[n];
visited[src] = true;

int dis = -1;                               // 1
while (!queue.isEmpty()) {
    dis++;                                  // 2
    for (int i=queue.size(); i>0; i--) {    // 3
        int u = queue.poll();

        // `dis` is the distance between `src` and `u`

        for (int v:g[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            queue.offer(v);
        }
    }                                       // 4
}