Na nossa nona aula de métodos computacionais discutimos os algoritmos BFS e DFS que promovem busca exaustiva em grafos e várias de suas aplicações. Esses são os slides usados em sala.
Abaixo temos os exemplos apresentados em sala de aula:
Análise empírica de redes
Como implementar o algoritmo de busca exaustiva em grafos conhecido como breadth first search - BFS (busca em largura)?
Como implementar o algoritmo de busca exaustiva em grafos conhecido como depth first search - DFS (Busca em profundidade)?
Referências Adicionais para essa aula:
Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seção 3.5]
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 22]
Referências complementares para essa aula:
Networks: An Introduction - Mark Newman
Soluções de exercícios:
Como implementar BFS e DFS em Python e extrair informações úteis de um grafo, como conectividade, aciclicidade, etc?