Busca em Largura

A busca em largura (BFS) explora um grafo sem pesos em camadas de distância crescente, em número de arestas, a partir de uma origem.

static int[] distances(List<List<Integer>> graph, int source) {
    int[] distance = new int[graph.size()];
    Arrays.fill(distance, -1);
    Queue<Integer> frontier = new ArrayDeque<>();
    distance[source] = 0;
    frontier.add(source);

    while (!frontier.isEmpty()) {
        int vertex = frontier.remove();
        for (int neighbor : graph.get(vertex)) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[vertex] + 1;
                frontier.add(neighbor);
            }
        }
    }
    return distance;
}

Correção

A fila contém vértices descobertos em ordem não decrescente de distância. Quando um vértice à distância d descobre um novo vizinho, cria-se um caminho de comprimento d + 1. Qualquer caminho menor teria descoberto esse vizinho a partir de uma camada anterior; portanto, a primeira distância atribuída é mínima.

Cada vértice alcançável entra na fila uma vez, e cada aresta de saída é inspecionada uma vez: tempo Θ(V + E) sobre o grafo representado e espaço auxiliar Θ(V). Armazene um predecessor junto à distância para reconstruir caminhos mínimos.

Observação

A BFS minimiza o número de arestas. Ela não resolve caminhos mínimos com pesos arbitrários; use Dijkstra somente quando os pesos não forem negativos.