Busca em Largura

Busca em largura ou em amplitude(Breadth for Search) é um dos algoritmos essenciais para busca e travessia em grafos.

Como uma consequência de como o algoritmo funciona, o caminho encontrado pela BFS para qualquer nó é o caminho mais curto para aquele nó, ou seja, o caminho que contém o menor número de arestas em um grafo sem pesos nas arestas.

O algoritmo funciona em tempo $O(n+m)$, no qual $n$ é o número de vértices e $m$ é o número de arestas.

Descrição

O algoritmo recebe como entrada um grafo sem pesos e o índice de um vértice fonte $s$. O grafo recebido na entrada pode ser direcionado ou indirecionado, não importa para o algoritmo.

O algoritmo pode ser entendido como um incêndio no grafo: na etapa inicial apenas o vértice fonte $s$ está em chamas. Em cada passo, o fogo vai incendiando cada vértice no mesmo nível e então alastra-se para todos os seus vizinhos conectados. Em uma iteração do algoritmo, o "anel de fogo" é expandido em largura por uma unidade.

Você pode visualizar melhor aqui.

Mais precisamente, o algoritmo pode ser declarado como: crie uma queue $q$ que irá conter os vértices a serem processados e uma array de booleanos $usados[]$ que irá indicar para cada vértice se ele foi incendiado(visitado) ou não.

Inicialmente, coloque o vértice fonte $s$ na queue e declare $usados[s] = true$, e para todos os outros vértices $v$ declare $usados[v] = false$. Então, o loop é executado até que a queue esteja vazia e em cada iteração ele vai excluindo um vértice da queue. Itere por todas as arestas saindo desse vértice e se alguma dessas arestas revelarem vértices não incendiados, declare-os "em chamas" e coloque eles dentro da queue.

Como consequência, quando a queue estiver vazia, o "anel de fogo" contém todos os vértices alcançáveis pela fonte $s$, com cada vértice alcançado no menor caminho possível. Você também pode calcular o tamanho dos caminhos(que apenas requer manter uma array das distâncias dos caminhos $d[]$) como também salvar informações para restaurar todos estes caminhos (para isso, é necessário manter uma array de "parentes" $p[]$, que guarda, para cada vértice, o vértice no qual alcançamos).

Implementação

vector<vector<int>> g;  // grafo como lista de adjacência
int n; // número de nós
int s; // vértice fonte

queue<int> q;
vector<bool> usados(n);
vector<int> d(n), p(n);

q.push(s);
usados[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : g[v]) {
        if (!usados[u]) {
            usados[u] = true;
            q.push(u);  //na bfs vamos apenas puxando os nós filhos para a queue, na dfs chamamos a função para ir mais fundo no grafo
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

Se tivermos que restaurar e exibir o menor caminho da fonte até algum vértice $u$, pode ser feito na seguinte maneira:

if (!usados[u]) {
    cout << "Sem caminho!";
} else {
    vector<int> caminhos;
    for (int v = u; v != -1; v = p[v])
        caminhos.push_back(v);
    reverse(caminhos.begin(), caminhos.end());
    cout << "Caminhos: ";
    for (int v : caminhos)
        cout << v << " ";
}

Aplicações de BFS

Problemas