Equipe Rust Brasil 9 min de leitura

Busca em Largura (BFS) em Rust

Implementação completa da Busca em Largura (BFS) em Rust com VecDeque, diagramas visuais, análise Big-O e exemplos práticos de grafos.

rust algoritmos grafos bfs busca-em-largura

A Busca em Largura (Breadth-First Search, ou BFS) é um dos algoritmos fundamentais para exploração de grafos. Ela percorre todos os vértices de um grafo nível por nível, visitando primeiro todos os vizinhos diretos de um vértice antes de avançar para os vizinhos dos vizinhos. Isso garante que, em grafos sem peso nas arestas, o BFS encontra o caminho mais curto (menor número de arestas) entre o vértice de origem e qualquer outro vértice alcançável.

Na prática, o BFS é usado em sistemas de navegação GPS (para grafos sem peso), crawlers de web, redes sociais (para encontrar grau de separação entre pessoas), resolução de quebra-cabeças como o cubo mágico, e em algoritmos de rede como o cálculo de fluxo máximo. Em Rust, a implementação é especialmente elegante graças ao VecDeque, que fornece operações eficientes de fila.

Como Funciona

O BFS utiliza uma fila (FIFO — First In, First Out) para controlar a ordem de visitação. O processo segue estes passos:

  1. Enfileira o vértice de origem e o marca como visitado.
  2. Desenfileira o próximo vértice da fila.
  3. Para cada vizinho não visitado, marca como visitado e enfileira.
  4. Repete os passos 2-3 até que a fila esteja vazia.

Diagrama Visual — Travessia Nível por Nível

Considere o seguinte grafo:

        0
       / \
      1   2
     / \   \
    3   4   5
        |
        6

Lista de adjacência:

0 -> [1, 2]
1 -> [0, 3, 4]
2 -> [0, 5]
3 -> [1]
4 -> [1, 6]
5 -> [2]
6 -> [4]

Execução do BFS a partir do vértice 0:

Passo  | Fila (frente -> trás) | Visitados          | Ação
-------|-----------------------|--------------------|---------------------------
  1    | [0]                   | {0}                | Enfileira origem 0
  2    | [1, 2]                | {0, 1, 2}          | Desenfileira 0, enfileira vizinhos 1, 2
  3    | [2, 3, 4]             | {0, 1, 2, 3, 4}    | Desenfileira 1, enfileira vizinhos 3, 4
  4    | [3, 4, 5]             | {0, 1, 2, 3, 4, 5} | Desenfileira 2, enfileira vizinho 5
  5    | [4, 5]                | {0, 1, 2, 3, 4, 5} | Desenfileira 3, sem novos vizinhos
  6    | [5, 6]                | {0,1,2,3,4,5,6}    | Desenfileira 4, enfileira vizinho 6
  7    | [6]                   | {0,1,2,3,4,5,6}    | Desenfileira 5, sem novos vizinhos
  8    | []                    | {0,1,2,3,4,5,6}    | Desenfileira 6, fila vazia -> FIM

Ordem de visitação por nível:

Nível 0:  [0]
Nível 1:  [1, 2]
Nível 2:  [3, 4, 5]
Nível 3:  [6]

Representação do Grafo

Em Rust, a forma mais comum de representar um grafo para BFS é com lista de adjacência usando Vec<Vec<usize>> para grafos com vértices numerados, ou HashMap<T, Vec<T>> para vértices de tipo genérico.

use std::collections::HashMap;

// Grafo com lista de adjacência usando HashMap
fn criar_grafo() -> HashMap<usize, Vec<usize>> {
    let mut grafo = HashMap::new();
    grafo.insert(0, vec![1, 2]);
    grafo.insert(1, vec![0, 3, 4]);
    grafo.insert(2, vec![0, 5]);
    grafo.insert(3, vec![1]);
    grafo.insert(4, vec![1, 6]);
    grafo.insert(5, vec![2]);
    grafo.insert(6, vec![4]);
    grafo
}

// Grafo com lista de adjacência usando Vec<Vec<usize>>
fn criar_grafo_vec(num_vertices: usize) -> Vec<Vec<usize>> {
    let mut grafo = vec![vec![]; num_vertices];
    // Aresta bidirecional entre 0 e 1
    grafo[0].push(1);
    grafo[1].push(0);
    // ... demais arestas
    grafo
}

Complexidade

CasoTempoEspaço
MelhorO(1)O(V)
MédioO(V + E)O(V)
PiorO(V + E)O(V)

Onde V = número de vértices e E = número de arestas.

  • Tempo O(V + E): cada vértice é enfileirado e desenfileirado no máximo uma vez (O(V)), e cada aresta é examinada no máximo uma vez ao verificar vizinhos (O(E)).
  • Espaço O(V): a fila e o conjunto de visitados podem conter até V elementos no pior caso.
  • Melhor caso O(1): quando o vértice de destino é o próprio vértice de origem.

Implementação em Rust

BFS Básico — Ordem de Visitação

use std::collections::{HashSet, VecDeque};

/// Realiza BFS a partir de `origem` e retorna a ordem de visitação.
fn bfs_ordem(grafo: &Vec<Vec<usize>>, origem: usize) -> Vec<usize> {
    let mut visitados = HashSet::new();
    let mut fila = VecDeque::new();
    let mut ordem = Vec::new();

    visitados.insert(origem);
    fila.push_back(origem);

    while let Some(vertice) = fila.pop_front() {
        ordem.push(vertice);

        for &vizinho in &grafo[vertice] {
            if !visitados.contains(&vizinho) {
                visitados.insert(vizinho);
                fila.push_back(vizinho);
            }
        }
    }

    ordem
}

fn main() {
    // Grafo com 7 vértices (0 a 6)
    let mut grafo = vec![vec![]; 7];

    // Arestas bidirecionais
    let arestas = [(0,1), (0,2), (1,3), (1,4), (2,5), (4,6)];
    for (u, v) in arestas {
        grafo[u].push(v);
        grafo[v].push(u);
    }

    let ordem = bfs_ordem(&grafo, 0);
    println!("Ordem de visitação BFS: {:?}", ordem);
    // Saída: Ordem de visitação BFS: [0, 1, 2, 3, 4, 5, 6]
}

BFS com Caminho Mínimo

use std::collections::{HashMap, HashSet, VecDeque};

/// Encontra o caminho mais curto entre `origem` e `destino` usando BFS.
/// Retorna None se não houver caminho.
fn bfs_caminho_minimo(
    grafo: &Vec<Vec<usize>>,
    origem: usize,
    destino: usize,
) -> Option<Vec<usize>> {
    if origem == destino {
        return Some(vec![origem]);
    }

    let mut visitados = HashSet::new();
    let mut fila = VecDeque::new();
    // Mapeia cada vértice ao seu predecessor no caminho
    let mut predecessor: HashMap<usize, usize> = HashMap::new();

    visitados.insert(origem);
    fila.push_back(origem);

    while let Some(vertice) = fila.pop_front() {
        for &vizinho in &grafo[vertice] {
            if !visitados.contains(&vizinho) {
                visitados.insert(vizinho);
                predecessor.insert(vizinho, vertice);
                fila.push_back(vizinho);

                // Encontrou o destino — reconstrói o caminho
                if vizinho == destino {
                    let mut caminho = vec![destino];
                    let mut atual = destino;
                    while let Some(&pred) = predecessor.get(&atual) {
                        caminho.push(pred);
                        atual = pred;
                    }
                    caminho.reverse();
                    return Some(caminho);
                }
            }
        }
    }

    None // Não há caminho entre origem e destino
}

fn main() {
    let mut grafo = vec![vec![]; 7];
    let arestas = [(0,1), (0,2), (1,3), (1,4), (2,5), (4,6)];
    for (u, v) in arestas {
        grafo[u].push(v);
        grafo[v].push(u);
    }

    match bfs_caminho_minimo(&grafo, 0, 6) {
        Some(caminho) => println!("Caminho mínimo de 0 a 6: {:?}", caminho),
        None => println!("Não há caminho entre 0 e 6"),
    }
    // Saída: Caminho mínimo de 0 a 6: [0, 1, 4, 6]

    match bfs_caminho_minimo(&grafo, 3, 5) {
        Some(caminho) => println!("Caminho mínimo de 3 a 5: {:?}", caminho),
        None => println!("Não há caminho entre 3 e 5"),
    }
    // Saída: Caminho mínimo de 3 a 5: [3, 1, 0, 2, 5]
}

BFS — Componentes Conexos

use std::collections::{HashSet, VecDeque};

/// Encontra todos os componentes conexos do grafo.
fn componentes_conexos(grafo: &Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let n = grafo.len();
    let mut visitados = HashSet::new();
    let mut componentes = Vec::new();

    for vertice in 0..n {
        if !visitados.contains(&vertice) {
            // BFS para encontrar todos os vértices deste componente
            let mut componente = Vec::new();
            let mut fila = VecDeque::new();

            visitados.insert(vertice);
            fila.push_back(vertice);

            while let Some(v) = fila.pop_front() {
                componente.push(v);
                for &vizinho in &grafo[v] {
                    if !visitados.contains(&vizinho) {
                        visitados.insert(vizinho);
                        fila.push_back(vizinho);
                    }
                }
            }

            componentes.push(componente);
        }
    }

    componentes
}

fn main() {
    // Grafo com 8 vértices, dois componentes desconexos
    let mut grafo = vec![vec![]; 8];
    // Componente 1: 0-1-2-3
    grafo[0].push(1); grafo[1].push(0);
    grafo[1].push(2); grafo[2].push(1);
    grafo[2].push(3); grafo[3].push(2);
    // Componente 2: 4-5-6-7
    grafo[4].push(5); grafo[5].push(4);
    grafo[5].push(6); grafo[6].push(5);
    grafo[6].push(7); grafo[7].push(6);

    let comps = componentes_conexos(&grafo);
    println!("Número de componentes: {}", comps.len());
    for (i, comp) in comps.iter().enumerate() {
        println!("Componente {}: {:?}", i + 1, comp);
    }
    // Saída:
    // Número de componentes: 2
    // Componente 1: [0, 1, 2, 3]
    // Componente 2: [4, 5, 6, 7]
}

Exemplo de Execução

Usando o BFS com caminho mínimo no seguinte grafo:

    0 --- 1 --- 3
    |     |
    2     4 --- 6
    |
    5

Buscando o caminho de 5 a 6:

Passo 1: Fila=[5], Visitados={5}
Passo 2: Desenfileira 5 -> vizinho 2 (novo)
         Fila=[2], Visitados={5, 2}, Predecessor: {2: 5}

Passo 3: Desenfileira 2 -> vizinhos 0 (novo), 1 (novo? não, veja lista adj.)
         Supondo adj: 2->[0,5], já visitou 5
         Fila=[0], Visitados={5, 2, 0}, Predecessor: {2:5, 0:2}

Passo 4: Desenfileira 0 -> vizinhos 1 (novo), 2 (já visitado)
         Fila=[1], Visitados={5, 2, 0, 1}, Predecessor: {2:5, 0:2, 1:0}

Passo 5: Desenfileira 1 -> vizinhos 0 (visitado), 3 (novo), 4 (novo)
         Fila=[3, 4], Predecessor: {..., 3:1, 4:1}

Passo 6: Desenfileira 3 -> sem novos vizinhos
         Fila=[4]

Passo 7: Desenfileira 4 -> vizinho 6 (novo) -> DESTINO ENCONTRADO!
         Predecessor: {..., 6:4}

Reconstrução: 6 <- 4 <- 1 <- 0 <- 2 <- 5
Caminho: [5, 2, 0, 1, 4, 6]  (comprimento = 5 arestas)

Variações e Otimizações

1. BFS Bidirecional

Executa BFS simultaneamente da origem e do destino, parando quando as duas buscas se encontram. Reduz o espaço de busca de O(b^d) para O(b^(d/2)), onde b é o fator de ramificação e d é a profundidade. Muito usado em grafos grandes como redes sociais.

2. BFS em Grade (Matriz)

Para problemas em matrizes 2D (labirintos, mapas), cada célula é um vértice e os vizinhos são as 4 (ou 8) células adjacentes. Não é necessário construir lista de adjacência explícita.

// Direções: cima, baixo, esquerda, direita
const DIRECOES: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

3. BFS 0-1

Para grafos com arestas de peso 0 ou 1, usa-se um VecDeque onde arestas de peso 0 são adicionadas na frente e arestas de peso 1 são adicionadas no final. Resolve o caminho mínimo em O(V + E) sem precisar de Dijkstra.

Quando Usar

Use BFS quando:

  • Precisa do caminho mais curto em grafos sem peso (ou com todas as arestas de peso igual).
  • Quer explorar vértices nível por nível (por exemplo, encontrar todos os amigos a 2 graus de distância).
  • Precisa encontrar componentes conexos de um grafo.
  • Está resolvendo problemas em grades/matrizes como inundação (flood fill) ou menor caminho em labirinto.
  • Precisa verificar se um grafo é bipartido (2-colorível).

Evite BFS quando o grafo tem arestas com pesos diferentes (use Dijkstra ou Bellman-Ford) ou quando precisa explorar caminhos profundos primeiro (use DFS).

Comparação com Outros Algoritmos

CaracterísticaBFSDFSDijkstra
Estrutura de dadosFila (VecDeque)Pilha/RecursãoFila de prioridade
Caminho mínimo (sem peso)SimNaoSim (mas overkill)
Caminho mínimo (com peso)NaoNaoSim
Complexidade de tempoO(V + E)O(V + E)O((V + E) log V)
Complexidade de espaçoO(V)O(V)O(V)
Detecção de ciclosSim (com adaptação)Sim (natural)Nao
Grafos desconexosPrecisa iterar vérticesPrecisa iterar vérticesApenas do vértice fonte
Ordem topológicaSim (Kahn)SimNao

Exercícios Práticos

  1. Distância mínima em grade: Dada uma matriz 0/1 onde 0 é caminho livre e 1 é parede, encontre a menor distância do canto superior esquerdo ao canto inferior direito usando BFS.

  2. Número de ilhas: Dada uma matriz 2D de '1' (terra) e '0' (água), conte o número de ilhas usando BFS. Uma ilha é um grupo de '1' conectados horizontalmente ou verticalmente.

  3. Verificação de grafo bipartido: Implemente um algoritmo que usa BFS para verificar se um grafo é bipartido (pode ser colorido com 2 cores sem que vértices adjacentes tenham a mesma cor).

  4. Palavra mais próxima: Dado um dicionário de palavras e duas palavras (origem e destino), encontre a menor sequência de transformações (mudando uma letra por vez) da origem ao destino, onde cada palavra intermediária deve existir no dicionário.

Veja Também