No mundo dos algoritmos, o BFS (Breadth-First Search ou Busca em Largura) é uma técnica fundamental quando queremos explorar caminhos em um grafo de maneira eficiente. Essa abordagem permite encontrar o menor caminho entre dois pontos, e "menor caminho" pode significar diversas coisas:
- O menor número de movimentos para atingir um resultado específico;
- O menor número de passos para ir de um ponto A até um ponto B;
- A provável próxima letra em uma sequência de palavras, entre outros.
O que é um Grafo?
Ao estudar o BFS, nos deparamos com uma estrutura de dados essencial: o grafo. Ele é composto por vértices (ou nós), que representam os elementos do problema, e arestas, que indicam as conexões entre esses elementos.
Por exemplo, imagine que temos um ponto A conectado a um ponto B:
Nesse caso, dizemos que A e B são vizinhos, pois estão conectados diretamente por uma aresta.
A Diferença entre BFS e Busca Binária
Se você já estudou algoritmos, provavelmente conhece a Busca Binária, muito utilizada para encontrar elementos em listas ordenadas, utilizando a estratégia de dividir para conquistar. No entanto, a BFS tem um propósito diferente:
Ela responde à pergunta: "Consigo sair do ponto A e chegar ao ponto B? Se sim, qual o menor número de passos necessários?"
Agora, vamos visualizar melhor esse conceito com um exemplo:
No primeiro exemplo, temos um caminho direto entre A e B. Mas, conforme o grafo se torna mais complexo, encontrar o menor caminho se torna um desafio maior.
Implementando o BFS em Java
Agora, vamos construir um exemplo prático de BFS em Java.
Representação do Grafo
Podemos representar um grafo de várias formas. Aqui, utilizaremos um HashMap, onde cada chave representa um nó e os valores associados são as listas de seus vizinhos:
var graph = new HashMap<String, List<String>>();
graph.put("Voce", List.of("Alice", "Bob", "Claire"));
graph.put("Bob", List.of("Anuj", "Peggy"));
graph.put("Alice", List.of("Peggy"));
graph.put("Claire", List.of("Thom", "Jonny"));
graph.put("Anuj", List.of());
graph.put("Peggy", List.of());
graph.put("Thom", List.of());
graph.put("Jonny", List.of());
Agora que temos nosso grafo, vamos implementar a busca.
Implementação do Algoritmo
Criamos uma fila para armazenar os nós a serem visitados. Como BFS segue a lógica FIFO (First In, First Out), essa estrutura é essencial para garantir que os nós sejam processados na ordem correta.
private static void example(Map<String, List<String>> graph) {
var filaDeBusca = new ArrayList<>(graph.get("Voce"));
var verificados = new HashSet<String>();
while (!filaDeBusca.isEmpty()) {
String first = filaDeBusca.remove(0);
// Se o nó já foi verificado, pulamos para o próximo
if (verificados.contains(first)) {
continue;
}
// Lógica de verificação do elemento desejado
if (first.startsWith("Jon")) {
System.out.println("Encontrado: " + first);
break;
}
verificados.add(first);
filaDeBusca.addAll(Optional.ofNullable(graph.get(first)).orElseGet(List::of));
}
}
Explicação do Código
- Criamos uma fila de busca contendo os vizinhos diretos do nó inicial.
- Criamos um conjunto de verificados para evitar visitar o mesmo nó mais de uma vez.
- Enquanto a fila não estiver vazia, retiramos o primeiro elemento e verificamos se ele atende ao critério desejado.
- Se for o nó procurado, encerramos a busca.
- Caso contrário, adicionamos seus vizinhos à fila e marcamos o nó como verificado.
Melhorias e Considerações
- A lógica de verificação pode ser personalizada para diferentes problemas.
- O uso de Set para armazenar os nós visitados evita laços infinitos e repetições desnecessárias.
- Se fosse necessário armazenar o caminho percorrido, poderíamos modificar a estrutura para incluir essa informação.
Conclusão
O algoritmo BFS é uma ferramenta poderosa para encontrar caminhos mínimos em grafos. Ele tem diversas aplicações, como em redes sociais, roteamento de mapas e até mesmo na IA de jogos.
Espero que esse artigo tenha ajudado a compreender melhor o BFS! Caso tenha dúvidas ou sugestões, deixe seu comentário.
Código Fonte: LuLiveira
Top comments (0)