LogRitmo navegador / ativofase / 02LR / fase 02 · ativaSiga um ramo até o fim antes de voltar e tentar outro.
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.
Depth-First Search (DFS) é uma travessia: visita nós sem usar pesos para decidir o próximo passo. Use para exploração, detecção de ciclos e problemas naturalmente recursivos.
pilha em profundidade
DFS explora um ramo até onde consegue antes de voltar; visitar primeiro não significa ter o menor custo.
Com lista de adjacência, explora componentes e dependências; 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.
Depth-First Search segue uma aresta disponível para dentro antes de procurar alternativas. A pilha explícita — ou a pilha de chamadas da versão recursiva — guarda os ramos ainda abertos. Quando um ramo não tem vizinhos inéditos, o retorno libera a próxima alternativa sem apagar a história da exploração.
Ao descobrir um vértice, DFS o marca antes de avançar. Assim, uma aresta que retorna a um vértice ativo ou já finalizado não inicia uma nova visita. Em uma componente alcançável, cada vértice entra na travessia no máximo uma vez.
O tempo de descoberta registra quando o vértice entra na exploração; o tempo de término registra quando todos os seus vizinhos foram considerados. Esse intervalo descreve o aninhamento dos ramos e permite raciocinar sobre ciclos, subárvores e dependências.
Para cobrir um grafo desconexo, é preciso iniciar uma nova raiz para cada vértice ainda não visitado. O resultado é uma floresta de DFS: uma árvore por componente alcançável ou, em grafos dirigidos, por início ainda pendente.
O(V + E) examina a rede; a pilha guarda o caminho ativo.Com lista de adjacência, cada vértice é descoberto uma vez e cada relação é examinada em tempo constante, para um custo de O(V + E). As marcas, os tempos e a pilha usam O(V) adicional. A versão recursiva também consome a pilha de chamadas: em um ramo muito profundo, esse limite de ambiente precisa ser considerado.
Em digrafos, uma aresta para um vértice ainda ativo evidencia um ciclo de retorno. Os tempos de término sustentam uma ordenação topológica apenas quando não há ciclos. Já em grafos não ponderados, se a pergunta for sobre o menor número de saltos, a exploração por camadas de BFS é o contrato adequado.
Escolha DFS para detectar ciclos, decompor componentes, explorar dependências e produzir uma ordenação topológica em um digrafo acíclico. Prefira BFS para minimizar o número de arestas em grafo não ponderado. Para minimizar custo com pesos não negativos, use Dijkstra. A ordem dos vizinhos pode alterar a árvore visual de DFS, mas não invalida as marcas, a cobertura da componente ou a classificação estrutural feita com os estados corretos.
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 dfs(graph, start, goal) { // Explore one branch before backtrackingconst stack = [start];const visited = new Set();while (stack.length) {const node = stack.pop();if (visited.has(node)) continue;visited.add(node);if (node === goal) return node;for (const next of graph[node]) stack.push(next);}return null;}