LogRitmo navegador / ativofase / 02LR / fase 02 · ativaExpanda em camadas, como uma onda que mede distância.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
Breadth-First Search (BFS) é uma travessia: visita nós sem usar pesos para decidir o próximo passo. Use em redes não ponderadas quando a primeira chegada representa o menor número de arestas.
fila por camadas
BFS encontra menor caminho em número de arestas quando o grafo não tem pesos relevantes.
Com lista de adjacência, é ideal para menor caminho em grafos sem pesos; a bancada usa um grafo pequeno e uma lista fixa de arestas para tornar cada visita visível.
V é o número de vértices (nós) e E é o número de arestas (ligações). BFS e DFS visitam cada parte necessária do grafo uma vez.
Adicionar nós e ligações aumenta o trabalho de forma proporcional ao tamanho da rede explorada.Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para comparar a exploração de um grafo não ponderado com o custo adicional de priorizar caminhos de menor distância. Breadth-First Search tende a crescer mais devagar do que Dijkstra quando aumentam vértices (V) e arestas (E). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
Breadth-First Search não escolhe o próximo nó por peso, por geometria ou por uma previsão. A fila FIFO mantém primeiro os nós descobertos mais perto da fonte. Por isso, em um grafo não ponderado, cada primeira descoberta representa o menor número possível de arestas até aquele nó.
A fonte começa na distância zero. Ao remover um nó de distância k, cada vizinho inédito entra com distância k + 1. Nós já descobertos da mesma camada deixam a fila antes dos nós mais distantes.
Quando um vizinho entra na fila, ele já recebe visited, parent e sua distância. Em ciclos, isso impede novas cópias do mesmo nó; em rotas concorrentes, preserva a primeira chegada, que é mínima em quantidade de arestas.
Seguir parent do destino até a fonte reconstrói um caminho mínimo. Se houver várias rotas com o mesmo número de arestas, a ordem dos vizinhos pode mudar o predecessor escolhido, sem alterar a distância correta.
O(V + E) percorre relações; não torna a fronteira gratuita.Com lista de adjacência, cada vértice é descoberto no máximo uma vez e cada aresta é examinada em tempo constante, resultando em O(V + E). A fila, as marcas, as distâncias e os predecessores usam O(V) adicional. Em grafos muito ramificados, a largura de uma camada pode concentrar boa parte dessa memória na fronteira.
BFS é apropriado para labirintos com movimentos unitários, graus de separação, alcance em rede e saídas mais próximas. Se uma aresta puder custar mais que outra, uma rota com menos passos pode ser mais cara. Nessa situação, a fila FIFO não substitui a prioridade por menor custo usada por Dijkstra.
Escolha BFS quando a pergunta for “quem chega em menos transições?” e cada transição tiver o mesmo custo. Para a saída mais próxima ou a fonte mais próxima, inicialize todas as fontes na fila com distância zero: a primeira descoberta mede a menor distância ao conjunto de origens. Em um digrafo, respeite a direção; em um grafo desconexo, reconheça que nós fora da componente alcançável permanecem sem rota a partir da fonte escolhida.
A mesma rede pode ser explorada com uma fila, uma pilha ou uma função de custo. Os trechos mostram o núcleo da decisão; funções de apoio, como recuperar a rota ou escolher o menor custo, aparecem com nomes descritivos para manter o foco da explicação.
function bfs(graph, start, goal) { // Explore the graph level by levelconst queue = [start];let head = 0;const visited = new Set([start]);while (head < queue.length) {const node = queue[head++];if (node === goal) return node;for (const next of graph[node]) {if (!visited.has(next)) {visited.add(next); queue.push(next);}}}return null;}