Solução Desafio Cartográfico

0 Flares Facebook 0 0 Flares ×

Este é um tipo de problema clássico: achar o diâmetro da uma árvore. Há duas versões diferentes para o problema: caso o grafo tenha peso nas arestas e caso não tenha. A primeira é consideravelmente mais fácil que a segunda, e é o caso do problema.

Para resolver o problema, fazemos os seguintes passos:

  • Fazer uma DFS ou BFS em um vértice qualquer (digamos, o 1).
  • Pegar o vértice v mais distante de 1 (é fácil notar que é uma folha)
  • Fazer uma DFS a partir de v e achar o mais distante
  • o diâmetro será a distância de v ao mais distante.

Vamos ao código:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: