Średnica drzewa

Średnica drzewa – najdłuższa ścieżka drzewa. W informatyce jej długość liczy się, stosując programowanie dynamiczne.

Aby obliczyć najdłuższą ścieżkę drzewa można dla dowolnego wierzchołka puścić BFS (Przeszukiwanie Grafu W Wszerz) .

Nazwijmy ten wierzchołek A.

Dla wierzchołka który będzie najdalej od wierzchołka początkowego A ,nazwijmy go B.

Od którego zaczynaliśmy poszukiwania odpalamy kolejnego BFS.

Wierzchołek do którego droga z wierzchołka B jest najdłuższa jest, najdłuższą ścieżką drzewa.

I w ten prosty sposób zawsze otrzymamy Średnice drzewa.

This article "Średnica drzewa" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Średnica drzewa.