Trabalho com grafos

Busca em profundidade

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafo, às vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Se o grafo for uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível. Existem dois métodos de percurso em grafos: percurso em profundidade (depth-first search — DFS) e o percurso em largura (breadth first search — BFS). A ideia básica do DFS é buscar "mais a fundo" no grafo quando possível. Assim, a partir de um vértice v, as arestas ainda não exploradas o são e, ao final, a busca retrocede. A ideia do BFS é bastante simples: os vértices do grafo são visitados nível a nível, ou seja, todos os vértices a uma distância k do vértice inicial são visitados antes de qualquer vértice a uma distância k +1 do inicial. 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