Busca em Largura (BFS - Breadth-First Search)

1. Explorando em Camadas

A BFS (Busca em Largura) é como jogar uma pedra num lago calmo: as ondas se propagam uniformemente em todas as direções. Ela explora o grafo em níveis a partir de um nó origem \(S\): 1. Primeiro visita \(S\) (Distância 0). 2. Depois todos os vizinhos diretos de \(S\) (Distância 1). 3. Depois os vizinhos dos vizinhos (Distância 2). 4. E assim por diante…

Por causa dessa propriedade, a BFS garante encontrar o Caminho Mínimo (menor número de arestas) em grafos não ponderados (ou com pesos iguais).

2. O Algoritmo

Utilizamos uma Fila (Queue) para gerenciar a ordem de visita (FIFO - First In, First Out).

Estados dos Vértices: - Não Visitado: Ainda não descoberto. - Visitado/Na Fila: Descoberto, mas seus vizinhos ainda não foram processados. - Processado: Já saiu da fila e seus vizinhos já foram checados.

Passo a Passo: 1. Inicialize um vetor visited[] como false e dist[] como \(\infty\). 2. Coloque o nó inicial \(S\) na Fila, marque visited[S] = true e dist[S] = 0. 3. Enquanto a Fila não estiver vazia: - Remova o elemento \(u\) da frente. - Para cada vizinho \(v\) de \(u\): - Se \(v\) não foi visitado: - Marque visited[v] = true. - Defina dist[v] = dist[u] + 1. - Adicione \(v\) na Fila.

3. Implementação em Java

Assumindo que temos a lista de adjacência List<List<Integer>> adj.

import java.util.*;

public class BFS {
    
    public static void bfs(int start, int V, List<List<Integer>> adj) {
        // Estruturas Auxiliares
        boolean[] visited = new boolean[V];
        int[] dist = new int[V];
        int[] parent = new int[V]; // Para reconstruir o caminho
        
        Arrays.fill(dist, -1); // -1 indica inalcançável
        Arrays.fill(parent, -1);
        
        // Configuração Inicial
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        dist[start] = 0;
        
        System.out.println("Iniciando BFS a partir de " + start);
        
        while (!queue.isEmpty()) {
            int u = queue.poll(); // Tira da frente
            // System.out.print(u + " "); // Ordem de visita
            
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    parent[v] = u; // Guardamos de onde viemos
                    queue.add(v);
                }
            }
        }
        
        // Exemplo: Imprimir distâncias
        for(int i=0; i<V; i++) {
            System.out.println("Distância de " + start + " para " + i + ": " + dist[i]);
        }
    }
    
    // Bônus: Reconstruir o caminho de Start até Target
    public static List<Integer> getPath(int target, int[] parent) {
        List<Integer> path = new ArrayList<>();
        if (parent[target] == -1) return path; // Sem caminho
        
        for (int v = target; v != -1; v = parent[v]) {
            path.add(v);
        }
        Collections.reverse(path); // O caminho foi montado de trás pra frente
        return path;
    }
}

Complexidade

  • Tempo: \(O(V + E)\). Cada vértice entra na fila uma vez e cada aresta é verificada duas vezes (uma por ponta, em grafos não direcionados).
  • Espaço: \(O(V)\) para a fila e vetores auxiliares.

4. BFS em Grids (Matrizes)

Muitos problemas (ex: labirintos) são dados como uma matriz, onde cada célula (r, c) é um vértice e vizinhos são (r+1, c), (r-1, c), etc.

Não precisamos criar uma Lista de Adjacência explícita. Usamos a matriz diretamente e vetores de direção.

// Direções: Cima, Direita, Baixo, Esquerda
int[] dr = {-1, 0, 1, 0};
int[] dc = {0, 1, 0, -1};

// Na BFS:
while(!queue.isEmpty()) {
    Point p = queue.poll();
    
    for(int i=0; i<4; i++) {
        int nr = p.r + dr[i];
        int nc = p.c + dc[i];
        
        if(isValid(nr, nc) && !visited[nr][nc]) {
            visited[nr][nc] = true;
            queue.add(new Point(nr, nc));
        }
    }
}

5. Multi-Source BFS

E se quisermos saber a qual a distância da “saída mais próxima” num labirinto com múltiplas saídas? Truque: Coloque todas as saídas na fila inicial com distância 0. A BFS vai expandir todas as “frentes de onda” simultaneamente. O primeiro a chegar num vértice define sua distância mínima para qualquer saída.

Aplicações Típicas: 1. Menor caminho em labirintos/mapas sem peso. 2. Checar conectividade (componentes conexos). 3. Web Crawlers (Explorar links nível a nível). 4. Algoritmo de fluxo Edmonds-Karp (usa BFS para achar caminho aumentante).

Back to top