Busca em profundidade

Na teoria dos grafos, busca em profundidade (ou busca em profundidade-primeiro, também conhecido em inglês por Depth-First Search - DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder(backtracking).

Uma versão da busca em profundidade foi investigada no século XIX pelo matemático francês Charles Pierre Trémaux^[1] como estratégia para solucionar labirintos.^[2]^[3]

Definição Formal

Representação visual de uma busca em profundidade

Formalmente, um algoritmo de busca em profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede (backtrack) e começa no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração.

A complexidade espacial de um algoritmo de busca em profundidade é muito menor que a de um algoritmo de busca em largura. A complexidade temporal de ambos algoritmos são proporcionais ao número de vértices somados ao número de arestas dos grafos aos quais eles atravessam.

Quando ocorrem buscas em grafos muito grandes, que não podem ser armazenadas completamente na memória, a busca em profundidade não termina, em casos onde o comprimento de um caminho numa árvore de busca é infinito. O simples artifício de “ lembrar quais nós já foram visitados ” não funciona, porque pode não haver memória suficiente. Isso pode ser resolvido estabelecendo-se um limite de aumento na profundidade da árvore.

Exemplo

Para o grafo ao lado, uma busca em profundidade começando em A, assumindo-se que as arestas esquerdas do grafo apresentado sejam escolhidas antes das arestas direitas, e assumindo que a busca relembre os nós previamente visitados e que não os repita (desde que este seja um grafo pequeno), visitaremos os nós na seguinte ordem : A, B, D, F, E, C, G.

Modificando essa mesma busca, sem que nos recordemos dos nós previamente visitados, teríamos como resultado a seguinte ordem de visita dos nós: A, B, D, F, E, A, B, D, F, E, etc, eternamente, já que a busca ficaria presa no ciclo A,B,D,F,E e nunca alcançaria G ou C.

O aprofundamento iterativo previne esse looping, alcançando os seguintes nós, nas seguintes profundidades, assumindo-se que ele prossiga da esquerda para a direita, como mostrado abaixo:

0: A
1: A (repetido), B, C, E

(Perceba que o aprofundamento iterativo agora enxergou C, ao passo que uma busca em profundidade convencional não enxergaria.)

2: A, B, D, F, C, G, E, F

(Perceba que a busca ainda enxerga C, mas que ele vem depois. Perceba também que ele enxerga E via diferentes caminhos, e passa duas vezes pelo F .)

3: A, B, D, F, E, C, G, E, F, B

Para esse grafo, quanto maior for a profundidade aplicada, os dois ciclos “ABFE” e “AEFB” simplesmente ficarão maiores, antes que o algoritmo desista e tente outro ramo.

Exemplos de Código

Um exemplo deste código gerado em C++ pode ser observado abaixo:

//By Said #include <iostream> #include <vector>  using namespace std;  #define MAXN 100100  int n, a, b, componete[MAXN]; vector< int > aresta[MAXN];  void dfs(int id){     componete[id] = -1;     for(int i = 0; i < aresta[id].size(); i++){         int v = aresta[id][i];         if(componete[v] == 0){             dfs(v);         }     } }  int main(){     cin >> n;     for(int i = 0; i < n; i++){         cin >> a >> b;         aresta[a].push_back(b);         aresta[b].push_back(a);     }     dfs(1);     return 0; }

Outro exemplo deste código gerado em JavaScript pode ser observado abaixo:

var saiu = 0;  function initDFS(nodos, inicio, fim){     i = inicio;     console.log(nodos[i]);     DFS(nodos, i, fim); };  function DFS(nodos, i, fim) {     nodos[i].visita = 2;     if (nodos[i].relIdObj == fim) {         console.log(nodos[i]);         saiu = 1;     };     if (nodos[i].relIdObj != fim && saiu == 0) {         for (var j = 0; j < nodos[i].filhosObj.length; j++) {             nodo = nodos[i].filhosObj[j].idVertice2;             if (nodo == fim && saiu == 0) {                 console.log(nodos[nodo]);                 saiu = 1;             };             if (nodos[nodo].visita != 2 && saiu == 0) {                 console.log(nodos[nodo]);                 DFS(nodos, nodos[nodo].relIdObj, fim);             };         };     }; };

Aplicações

Achar componentes conectados
Achar componentes fortemente conectados
Ordenação topológica
Resolução de quebra-cabeças como labirinto

Referências

↑ Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876)
Conferência pública, 2 de dezembro de 2010 – pelo professor Jean Pelletier-Thibert na Académie de Macon (Borgonha – França) – (Abstrato publicado nos anais da Academia, Março de 2011 – ISSN: 0980-6032)
↑ Even, Shimon (2011), Graph Algorithms, ISBN 978-0-521-73653-4 2nd ed. , Cambridge University Press, pp. 46–48 .
↑ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms, ISBN 978-0-201-36118-6 3rd ed. , Pearson Education .

Ver também

Busca em largura

Ligações externas

[1] Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876)
Conferência pública, 2 de dezembro de 2010 – pelo professor Jean Pelletier-Thibert na Académie de Macon (Borgonha – França) – (Abstrato publicado nos anais da Academia, Março de 2011 – ISSN: 0980-6032)

[2] Even, Shimon (2011), Graph Algorithms, ISBN 978-0-521-73653-4 2nd ed. , Cambridge University Press, pp. 46–48 .

[3] Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms, ISBN 978-0-201-36118-6 3rd ed. , Pearson Education .

[1]

[2]

[3]