Busca em profundidade (DFS)
Explora um grafo seguindo um caminho o mais fundo possível e depois volta à última bifurcação. A pilha na tela é esse caminho.
- O(V + E)
- memória O(V)
- pilha
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.
Pilha: o último a entrar é o primeiro a sair. A DFS sempre continua a partir do último vértice que alcançou.
Outros termos desta página
- Vértice: um ponto do grafo, desenhado aqui como um círculo com uma letra.
- Aresta: uma linha que liga dois vértices. Aqui dá para percorrê-la nos dois sentidos.
- Vizinhos: os vértices ligados a um vértice por uma aresta. São examinados em ordem alfabética.
Experimente: Escolha o grafo com ciclos. Cada aresta tracejada leva de volta a um vértice que já está na pilha ou pronto: essa aresta fecha um ciclo.
Como funciona
A DFS chama a si mesma no primeiro vizinho que ainda não viu, depois no primeiro vizinho novo desse vértice, e assim por diante. Quando um vértice não tem mais vizinhos novos, sua chamada termina e a DFS volta um passo para tentar o próximo vizinho. As chamadas abertas formam uma pilha, que é sempre o caminho do início até o vértice atual. O número ao lado de um vértice é a ordem em que ele foi visitado.
Quando é uma boa escolha
Use a DFS para descobrir o que dá para alcançar, encontrar ciclos, percorrer um labirinto ou ordenar tarefas que dependem umas das outras. Ela não encontra o caminho mais curto.