---
title: "Busca em Largura (BFS) em Rust"
url: "https://rustlang.com.br/algoritmos/bfs/"
markdown_url: "https://rustlang.com.br/algoritmos/bfs.MD"
description: "Implementação completa da Busca em Largura (BFS) em Rust com VecDeque, diagramas visuais, análise Big-O e exemplos práticos de grafos."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# 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.


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.

```rust
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

| Caso    | Tempo       | Espaço   |
|---------|-------------|----------|
| Melhor  | O(1)        | O(V)     |
| Médio   | O(V + E)    | O(V)     |
| Pior    | O(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

```rust
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

```rust
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

```rust
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.

```rust
// 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](/algoritmos/dijkstra/) ou [Bellman-Ford](/algoritmos/bellman-ford/)) ou quando precisa explorar caminhos profundos primeiro (use [DFS](/algoritmos/dfs/)).

## Comparação com Outros Algoritmos

| Característica            | BFS                    | DFS                    | Dijkstra               |
|---------------------------|------------------------|------------------------|------------------------|
| Estrutura de dados        | Fila (VecDeque)        | Pilha/Recursão         | Fila de prioridade     |
| Caminho mínimo (sem peso) | Sim                    | Nao                    | Sim (mas overkill)     |
| Caminho mínimo (com peso) | Nao                    | Nao                    | Sim                    |
| Complexidade de tempo     | O(V + E)               | O(V + E)               | O((V + E) log V)       |
| Complexidade de espaço    | O(V)                   | O(V)                   | O(V)                   |
| Detecção de ciclos        | Sim (com adaptação)    | Sim (natural)          | Nao                    |
| Grafos desconexos         | Precisa iterar vértices| Precisa iterar vértices| Apenas do vértice fonte|
| Ordem topológica          | Sim (Kahn)             | Sim                    | Nao                    |

## 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

- [`VecDeque` — Fila de duas pontas](/stdlib/vecdeque/) — estrutura de dados usada como fila no BFS
- [`HashMap` — Mapa hash](/stdlib/hashmap/) — para representação de grafos com lista de adjacência
- [`HashSet` — Conjunto hash](/stdlib/hashset/) — para rastrear vértices visitados
- [`Vec` — Vetor dinâmico](/stdlib/vec/) — para lista de adjacência e armazenamento de resultados
- [Busca em Profundidade (DFS)](/algoritmos/dfs/) — algoritmo complementar ao BFS
- [Algoritmo de Dijkstra](/algoritmos/dijkstra/) — caminho mínimo em grafos com peso
- [Ordenação Topológica](/algoritmos/topological-sort/) — usa BFS (Kahn) ou DFS