A busca em profundidade é um algoritmo que processualmente procura uma estrutura de gráfico ou árvore por viajar tão longe para baixo da árvore , pois ele pode antes de fazer backup . O tempo que leva o algoritmo de terminar depende do número de nós no gráfico . No pior caso , o algoritmo deve visitar cada nó no gráfico. Árvore Gráficos

No contexto de gráficos , uma árvore é um grafo em que cada nó , exceto a origem nó "root" tem um único nó pai cuja linhagem remonta ao nó raiz . O gráfico forma uma estrutura semelhante à de uma árvore de Natal , gradualmente expandindo e adicionar novos modos e crianças a cada nível . Em uma árvore , o número de filhos de cada nó tem é a árvore " fator de ramificação . " O número de gerações na árvore é " profundidade". Da árvore
Depth- First Search

a busca em profundidade é um método de pesquisa através de uma árvore, em que o algoritmo caminha pela árvore até encontrar o nó de destino. A partir do nó raiz , o algoritmo caminha até o próximo filho e , em seguida, neto dessa criança , repetindo o processo até que ele encontra um sem filhos "folha" nó. Depois de verificar que nó, ele caminha de volta para cima até encontrar um nó não examinada . Se não existem mais nós examinados , ele pára .
Algoritmo de tempo Complexidade

O tempo para percorrer uma árvore através de busca em profundidade depende do número de vértices do grafo e as arestas entre eles. No pior caso , o algoritmo deve viajar através de cada vértice e ao longo de cada borda , assim que o tempo que levará é o número de vértices eo número de arestas , ou " V + E. " Para uma árvore , o número de arestas é igual para os gânglios menos um , de modo que o tempo total é " 2V - 1." Se cada nó no gráfico tem o mesmo número de crianças - um factor de ramificação constante - então este tempo é igual ao fator elevado à potência de profundidade da árvore
Outras considerações

ao implementar qualquer algoritmo , a velocidade do algoritmo depende de dois fatores : . o número de cálculos que devem fazer eo tempo necessário para acessar os recursos de que necessita para funcionar - geralmente memória. Quanto mais memória um programa requer , o que leva mais tempo para ser executado. A busca em profundidade deve lembrar os nós anteriores, visitou, de modo que o pior caso de quantidade de memória que requer é igual ao número de nós na árvore.