Busca em profundidade

Busca em Profundidade
Explicação
É um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo, começando em um nó raiz e explorando tanto quanto possível cada um dos seus ramos, antes de retroceder.
Exemplo:

Para o grafo acima, 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.

Vantagens:
Facilidade de implementação
Pouco uso de memória
Desvantagens
Pode – se demorar muito a chegar a soluções

Busca em Profundidade Limitada
Definição
Este algoritmo opera como a busca em profundidade, porém ao invés de ficar examinando um determinado ramo indefinidamente, é colocado um limite na altura da árvore de busca.
Explicação e exemplos: