- Atual
- Na pilha
- Concluído
- Caminho
Pesquisa em profundidade (DFS)
A pesquisa em profundidade explora um grafo como alguém que percorre um labirinto com uma mão na parede: segue um caminho até onde ele vai, e só recua quando não há nada de novo para onde ir. Para isso, usa uma pilha. Clique num nó para começar a partir dele, escolha um destino se quiser, e avance passo a passo para ver a pilha crescer e encolher, cada nó receber o seu número de visita e as arestas que fecham um ciclo. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para procurar um caminho até ele. O número em cada nó é a ordem em que foi visitado, e a linha por baixo do grafo é a pilha, desde a origem até ao nó do topo. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Clique num nó para o tornar a origem. Para procurar um caminho, mude o clique para Destino e clique noutro nó.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
- Observe a pilha por baixo do grafo e o número de visita em cada nó. Novo grafo cria outro grafo para experimentar.
Como funciona a pesquisa em profundidade
Coloque o nó de origem na pilha. Depois repita: olhe para o vizinho seguinte do nó no topo da pilha. Um vizinho que ainda não foi visto recebe o número de visita seguinte, guarda o nó a partir do qual foi alcançado e passa para o topo da pilha, pelo que a pesquisa continua a partir daí. Quando o nó do topo já não tem vizinhos por verificar, fica concluído e sai da pilha, e a pesquisa recua para o nó de baixo. Quando a pilha fica vazia, todos os nós alcançáveis foram visitados.
O que a pilha lhe diz
Como a pesquisa continua sempre a partir do nó mais recente, a pilha é sempre um caminho desde a origem até ao nó que está a ser examinado. Quando o destino é alcançado, a pilha é um caminho até ele, embora normalmente não o mais curto: esse é encontrado pela pesquisa em largura. Num grafo não orientado, uma aresta para um nó que ainda está na pilha, sem ser aquele de onde se acabou de vir, fecha um ciclo. Os nós guardados formam uma árvore, a árvore da pesquisa em profundidade, e a ordem em que os nós ficam concluídos é a chave da ordenação topológica.
Perguntas frequentes
O que é a pesquisa em profundidade?
Uma forma de explorar um grafo a partir de um nó de origem, seguindo um caminho o mais fundo possível e recuando para experimentar outro ramo só quando não há nada de novo para onde ir. Usa uma pilha, ou recursão, para se lembrar do caminho de volta.
A pesquisa em profundidade encontra o caminho mais curto?
Não. Encontra um caminho até ao destino, se existir, mas esse caminho pode ser muito mais longo do que o necessário, porque a DFS se compromete com o primeiro ramo que experimenta. Use a pesquisa em largura para ter o menor número de arestas, ou o algoritmo de Dijkstra quando as arestas têm comprimentos.
Qual é a diferença entre DFS e BFS?
A pesquisa em profundidade usa uma pilha e vai fundo por um caminho antes de recuar. A pesquisa em largura usa uma fila e espalha-se de forma uniforme, anel a anel. Ambas visitam todos os nós alcançáveis num tempo que cresce com o número de nós mais o de arestas; a BFS encontra caminhos mais curtos, enquanto a DFS é a escolha natural para ciclos, labirintos e ordenação topológica.
Como é que a DFS encontra um ciclo?
Num grafo não orientado, se a pesquisa encontra uma aresta para um nó que ainda está na pilha, e esse nó não é aquele de onde acabou de vir, a aresta fecha um laço. Na aplicação, a linha de estado indica-o quando isso acontece.
O meu grafo é enviado para algum lado?
Não. O grafo é criado e percorrido no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor