Pesquisa em profundidade (DFS)
Entre num labirinto, continue até chegar a um beco sem saída, depois volte à última bifurcação e experimente o caminho seguinte. A pesquisa em profundidade explora um grafo da mesma forma. É um dos algoritmos de grafos mais simples, e a pilha que mantém diz mais do que se poderia esperar.
A ideia
Um grafo é um conjunto de nós ligados por arestas: salas e portas, páginas web e ligações, tarefas e as tarefas de que dependem. A pesquisa em profundidade visita todos os nós que consegue alcançar a partir de uma origem, mas por uma ordem especial: continua sempre a partir do nó que alcançou mais recentemente. Mantém uma pilha dos nós em que se encontra. Um nó novo vai para o topo, e um nó só sai quando tudo à sua volta foi explorado.
Passo a passo
Coloque a origem na pilha e dê-lhe o número de visita 1. Olhe para o vizinho seguinte do nó do topo. Se ainda não foi visto, dê-lhe o número de visita seguinte, guarde o nó a partir do qual foi alcançado e coloque-o no topo da pilha. Se já foi visto, ignore-o. Quando o nó do topo já não tem vizinhos por verificar, está concluído: retire-o e continue com o nó de baixo. Pare quando a pilha ficar vazia ou quando o destino for alcançado.
Um exemplo
Pegue num grafo com as arestas A–B, A–C, B–D, C–D, C–E e D–F, comece em A e verifique os vizinhos por ordem alfabética. De A a pesquisa vai para B, de B para D, de D para C e de C para E, por isso a pilha é A, B, D, C, E. Pelo caminho, C vê A, que ainda está na pilha: a aresta C–A fecha o ciclo A, B, D, C. E não tem nada de novo, por isso fica concluído, depois C, e a pesquisa recua para D, que ainda tem F. A ordem de visita é A, B, D, C, E, F. Com E como destino, a DFS para com o caminho A → B → D → C → E, quatro arestas, embora A → C → E precise só de duas.
Para que serve
A pilha é sempre um caminho desde a origem até ao nó atual, o que torna a DFS natural para labirintos e quebra-cabeças: é a ideia por trás do backtracking. Num grafo não orientado, uma aresta para um nó que ainda está na pilha fecha um ciclo. Num grafo orientado, listar os nós pela ordem inversa àquela em que ficam concluídos dá uma ordem topológica, de modo que cada tarefa vem depois das tarefas de que depende. A pesquisa em profundidade também encontra componentes conexas, pontes e pontos de articulação, e a sua versão aleatória é uma forma clássica de gerar labirintos.
História
No século XIX, o matemático francês Charles Pierre Trémaux descreveu uma forma de sair de qualquer labirinto marcando as passagens, o que é uma pesquisa em profundidade feita com giz. Em 1972 e 1973, Robert Tarjan e John Hopcroft mostraram que a DFS resolve muitos problemas de grafos em tempo linear, desde as componentes fortemente conexas até verificar se um grafo pode ser desenhado sem cruzamentos. Receberam o Prémio Turing de 1986 em parte por esse trabalho.
Experimente
Abra a aplicação e prima Avançar. O nó cujos vizinhos estão a ser verificados está realçado, os nós na pilha estão a azul e os concluídos a verde, cada um com o seu número de visita. A pilha aparece por baixo do grafo, desde a origem até ao nó do topo. Esteja atento à linha de estado para ver as arestas que fecham um ciclo, e escolha um destino para ver quão longo pode ser o caminho encontrado em comparação com a pesquisa em largura.
Perguntas frequentes
Qual é a complexidade temporal da DFS?
O(V + E) para V nós (vértices) e E arestas (edges, em inglês): cada nó entra e sai da pilha uma vez, e cada aresta é examinada a partir das duas pontas. Precisa de O(V) de memória extra para a pilha e as marcas.
Porque é que a DFS usa uma pilha?
Porque, com a regra o último a entrar é o primeiro a sair, a pesquisa continua a partir do nó mais recente e depois recua para o anterior. A recursão faz o mesmo com a pilha de chamadas do programa. Com uma fila em vez disso, a pesquisa espalhar-se-ia anel a anel: isso é a pesquisa em largura.
A DFS recursiva é um problema em grafos grandes?
Pode ser: um caminho longo significa uma recursão profunda, e muitas linguagens limitam a profundidade das chamadas. Uma versão iterativa, com uma pilha explícita, evita esse limite e visita os nós pela mesma ordem.
Onde é usada a DFS?
Na resolução de labirintos e quebra-cabeças por backtracking, na deteção de ciclos, na ordenação de tarefas pelas suas dependências (ordenação topológica), na procura de componentes conexas e fortemente conexas, na geração de labirintos, e em compiladores e ferramentas de build que percorrem grafos de dependências.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar a pesquisa em profundidade