Busca em largura (BFS) e busca em profundidade (DFS)

O que são grafos?

Grafos são um ramo da matemática que estuda relações entre objetos pertencentes a um determinado conjunto.

Você pode pensar, por exemplo, que $${a, b}$$ representa uma relação que leva de a para b.

Historicamente, Leonhard Euler, também responsável pela identidade de Euler,

$$E^{i\pi} + 1 = 0$$

publicou, em 1736, um artigo sobre o problema das sete pontes de Königsberg. Esse trabalho é considerado o ponto de partida da teoria dos grafos.

Onde grafos são usados?

Na computação, grafos aparecem direta ou indiretamente em muitos lugares:

redes neurais;
estruturas de árvores;
redes de computadores;
computação gráfica;
redes sociais.

Se um problema exige representar conexões, provavelmente um grafo será útil.

Isso fica ainda mais interessante em linguagens formais e autômatos, áreas fundamentais para a construção de linguagens de programação e marcação. Elas também usam grafos para representar autômatos e diagramas de transição.

Algoritmos de busca em grafos

Como um grafo é formado por relações, direcionadas ou não, precisamos definir um critério para percorrê-lo.

E para isso temos um problema essencial que precisa ser resolvido.

Qual critério?

Normalmente ou estamos trabalhando com grafos esparsos ou grafos densos.

Grafos esparsos têm poucas arestas em relação ao número de vértices.

Grafos densos, por sua vez, têm muitas arestas.

Essa característica influencia diretamente a escolha da representação e do algoritmo mais eficiente.

Os dois algoritmos mais clássicos para essa busca são:

BFS (Breadth-First Search): busca em largura;
DFS (Depth-First Search): busca em profundidade.

Algoritmos

Busca em Largura (BFS)

O algoritmo de busca em largura explora nível por nível.

Ou seja se pensarmos em uma árvore.

Ele verificaria primeiro os vizinhos da raiz.

Depois os vizinhos dos vizinhos da raiz e por assim vai.

Para fazer isso a gente utiliza uma estrutura de dados fila/queue.

Propriedades da busca em largura

Se existir uma solução, este algoritmo consegue encontrar.
Em grafos não ponderados, encontra o caminho com o menor número de arestas.
Complexidade:
Tempo: $$O(V + E)$$, pois percorre os vértices e as arestas alcançáveis.
Espaço: $$O(V)$$ porque precisa armazenar a fila e o conjunto de visitados.

Lógica passo a passo

Colocamos um nó na fila, e marcamos como visitado.
Enquanto a fila não estiver vazia:

Retiramos o primeiro elemento.
Visitamos todos os vizinhos não visitados do nó.
Adicionamos esses vizinhos à fila e os marcamos como visitados.

Busca em Profundidade

A busca em profundidade em comparação explora todo um ramo do grafo até o fim antes de voltar e explorar outros ramos.

Ao contrário da busca em largura, aqui usamos pilha/stack (Last In, First Out).

Propriedades da busca em profundidade

Em grafos finitos, consegue percorrer todos os vértices alcançáveis, mas não garante o caminho mais curto.
Ótimo? Não, não é adequado quando você precisa do menor número de arestas.
Complexidade:
- Tempo: $$O(V + E)$$
- Espaço: $$O(V)$$
Risco prático: a versão recursiva pode estourar a pilha em grafos muito profundos; nesses casos, prefira uma versão iterativa.

Lógica passo a passo

Marque o nó inicial como visitado e entre nele.
Para cada vizinho não visitado, repita o processo.
Quando o nó não tem vizinhos não visitados, realize um backtrack.
Continue até visitar todos os nós alcançáveis.

Conclusão

Não existe um algoritmo universalmente “melhor”: tudo depende do objetivo.

BFS (Busca em Largura):

Garante o menor caminho em grafos não ponderados.
Mais indicado quando o problema exige a solução mais curta.

DFS (Busca em Profundidade):

Útil para exploração completa, detecção de ciclos, ordenação topológica e backtracking.
Mais indicado quando queremos percorrer toda a estrutura ou analisar propriedades do grafo.

Ambos têm a mesma complexidade assintótica, $$O(V+E)$$, mas aplicam-se a cenários distintos.

E devem ser tratados com cautela para não escolher a pior opção por puro achismo.

Espero que tenham gostado do post. Valeu!