7. Aplicações
- Caminhos mínimos em grafos não ponderados
- Busca de caminho em grades (jogos, robótica)
- Conectividade e alcançabilidade
- Verificação de bipartição (duas cores)
- Componentes conexas (grafos não direcionados)
- Níveis, propagação e “graus de separação”
- Padrões de engenharia: roteamento, breadcrumbs, impacto de dependências
A BFS é um dos algoritmos de grafos mais práticos na engenharia. Sempre que as arestas representam custo unitário (um salto, um movimento, um passo), a BFS se torna a ferramenta padrão.
Nesta parte, conectamos a teoria a tarefas do mundo real que você verá em sistemas, produtos e entrevistas.
7.1 Caminhos Mínimos (Grafos Não Ponderados)
Se cada aresta tem o mesmo “custo” (1 salto), a BFS calcula as distâncias de caminho mínimo:
E os ponteiros de predecessor π permitem reconstruir o caminho (Parte 6).
7.2 Busca de Caminho em Grades (Jogos & Robótica)
Uma grade 2D pode ser modelada como um grafo:
- Cada célula é um vértice
- Arestas conectam movimentos válidos para vizinhos (vizinhança-4 ou vizinhança-8)
- Paredes/obstáculos removem vértices ou arestas
A BFS encontra o menor número de movimentos do início até o objetivo.
7.3 Alcançabilidade & Conectividade
A BFS responde: “consigo chegar lá a partir daqui?”:
- Execute BFS a partir de s
- Todos os vértices descobertos são alcançáveis
7.4 Componentes Conexas (Grafos Não Direcionados)
Para encontrar todas as componentes conexas:
- Marque todos os vértices como não visitados
- Para cada vértice não visitado, execute BFS e marque toda a sua componente
- Cada execução de BFS descobre exatamente uma componente
O tempo total permanece linear:
7.5 Verificação de Bipartição (Duas Cores)
A BFS pode testar se um grafo é bipartido usando duas cores por camadas:
- Atribua a cor A a s
- Todos os vizinhos devem ter a cor B
- Vizinhos de B devem ter A, e assim por diante
- Se uma aresta conecta vértices da mesma cor, o grafo não é bipartido
7.6 Níveis, Propagação e “Graus de Separação”
A BFS naturalmente calcula camadas:
Isso modela processos de espalhamento:
- Propagação de mensagens (saltos)
- Tempo mínimo em passos discretos de difusão
- Consultas do tipo “amigos a até 2 saltos”
7.7 Padrões de Engenharia
BFS é um padrão, não apenas um algoritmo:
- Roteamento por número de saltos: menor número de hops em redes overlay
- Breadcrumbs / ponteiros de pai: guardar pais para reconstruir caminhos ou navegação de UI
- Análise de impacto: “o que depende disso?” (grafos de dependência)
- Busca em espaço de estados: explorar transições com número mínimo de passos
Próxima: Parte 8 — BFS vs DFS
Já vimos o que a BFS faz e onde ela se destaca. Agora vamos colocá-la lado a lado com a Busca em Profundidade (DFS): como a ordem de exploração muda, quais estruturas cada uma produz, e como escolher a travessia certa para problemas de engenharia.