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:
https://gist.github.com/luccasiau/ee0caea68f1deaca7279
Deixe um comentário