Resumo

Nesta aula você conheceu duas abordagens distintas para realizar percursos em grafos: a busca em profundidade e a busca em largura.

Na busca em profundidade, você afunila uma sequência de vértices em um caminho até chegar no ponto desejado (se for possível!), fazendo várias idas e voltas a partir do ponto de origem do grafo. Essa abordagem é muito boa para implementar de forma recursiva, e adotar uma estratégia de backtracking para descobrir todos os caminhos possíveis entre dois vértices!

Na busca em largura, você observou um método mais sistemático de varredura do grafo, com o algoritmo partindo de um nó inicial e irradiando sua busca nos pontos mais próximos, expandindo gradativamente para os vértices mais distantes do grafo. Essa abordagem é muito boa para verificar se é possível chegar a um vértice específico do grafo a partir de diversos pontos distintos.

Ambos os algoritmos são eficientes em percorrer o grafo, mas nenhum deles leva em conta decisões de otimização necessárias para encontrar o caminho de menor custo entre dois vértices.

Na próxima aula você conhecerá dois algoritmos que são capazes de realizar essa tarefa.

Bons estudos!