Pesquisa em profundidade (DFS)
Explora um grafo seguindo um caminho até onde puder e depois volta à última bifurcação. A pilha no ecrã é esse caminho.
- tempo O(V + E)
- memória O(V)
- usa uma pilha
O que significam estes termos?
- Vértice: um ponto do grafo, desenhado aqui como um círculo com uma letra.
- Aresta: uma linha que liga dois vértices. Aqui pode ser percorrida nos dois sentidos.
- Vizinhos: os vértices ligados a um vértice por uma aresta. São examinados por ordem alfabética.
- Fila: o primeiro a entrar é o primeiro a sair. A BFS tira sempre o vértice que está há mais tempo à espera.
- Pilha: o último a entrar é o primeiro a sair. A DFS continua sempre a partir do último vértice a que chegou.
- V e E: o número de vértices e de arestas. O(V + E) significa que cada vértice e cada aresta são tratados um número fixo de vezes.
- na pilha
- atual
- terminado
- aresta da árvore de pesquisa
- aresta ignorada
Começamos em A. Carregue em Reproduzir ou avance passo a passo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha o grafo com ciclos. Cada aresta tracejada volta a um vértice que já está na pilha ou terminado: essa aresta fecha um ciclo.
Como funciona
A DFS chama-se a si própria com o primeiro vizinho que ainda não viu, depois com o primeiro vizinho novo desse vértice, e assim por diante. Quando um vértice já não tem vizinhos novos, a sua chamada termina e a DFS recua um passo para tentar o vizinho seguinte. As chamadas abertas formam uma pilha, que é sempre o caminho do início até ao vértice atual. O número junto a um vértice é a ordem em que foi visitado.
Quando é uma boa escolha
Use a DFS para saber o que se consegue alcançar, para encontrar ciclos, para percorrer um labirinto ou para ordenar tarefas que dependem umas das outras. Não encontra o caminho mais curto.