Please enable JavaScript.
Coggle requires JavaScript to display documents.
Busca em Largura (BFS) - Coggle Diagram
Busca em Largura (BFS)
Conceito fundamental
O que é: * A Busca em Largura(BFS) é um algoritmo de exploração de grafos que que visita todos os nós de um mesmo nível (distância do nó inicial) antes de avançar para os nós do próximo nível
Características principais:
- Estrutura de Dados: utiliza uma fila (queue) para armazenar nós a serem visitados(FIFO: First-In- First-Out) ;
- Completude: Garante encontrar uma solução se ela existir (para grafos finitos).
- Optimalidade: Encontra o caminho mais curto em termos de numero de arestas em grafos não ponderados.
Exemplo prático: Rede social: Encontrar a menor distância (menos conexões) entre dois perfis (ex: "Amigos de amigos)
Vantagens da BFS
Caminho mais Curto:
- Em grafos não ponderados, a BFS garante o caminho com menor número de arestas, pois explora todos os nós de nível antes de avançar. * Por quê? A primeira vez que um nó é alcançado, ele está menor caminho possível.
- Conectividade e ciclos: * Pode verificar se um grafo é conexo ( todos os nós são alcançáveis) e detectar ciclos.
-
Aplicações clássicas
- Labirintos : encontrar a saída mais próxima do ponto inicial. .
- Redes sociais: Determinar a menor cadeia de conexões entre usuários
- Grafos não ponderados : Caminhos mais curtos( ex: roteamento em redes)
- Verificação de Acessibilidade:: Verificar se todas as salas de um edifício são acessíveis a partir de uma entrada.
-
Comparação com outros algoritmos BFS: Estrutura: Fila; Caminho mais curto: sim (não ponderado) ; Memória: Alta(armazena níveis inteiros); DFS: Estrutura: Pilha(Stack); Caminho mais curto: Não garante ; Memória: Baixa(profundidade atual);
-