Witam,
nie wiem jak znaleźć średnicę drzewa, pomożecie mi w tym?
chodzi mi o informatyczne drzewo (od tego jest chyba ta strona)
0
1
Może ta odpowiedź ci pomoże:
http://forum.warsztat.gd/index.php?topic=23555.0
7
Ad usuniętych postów/komentarzy: jeśli ktoś nie rozumie pojęcia "średnicy drzewa" to może po prostu nie odpisywać, zamiast pisać o piłach i miarkach.
Ad pytania: prosty dynamiczny algorytm na drzewie.
Średnica drzewa T mającego dzieci L i R to
f(NULL) = 0
f(T) = max(h(L) + h(R) + 1, f(L), f(R))
Gdzie h(x) to wysokość poddrzewa
h(NULL) = 0
h(T) = 1 + max(h(L), h(R))
Wysokośc poddrzewa możesz liczyć jednocześnie ze średnicą, uważaj żeby z tego algorytmu nie zrobić O(n^2).
Wytłumaczenie algorytmu "po polsku" - są trzy opcje na średnicę drzewa:
- średnica całego drzewa zawiera sie w całości w lewym poddrzewie - wynikiem jest średnica lewego poddrzewa
- średnica całego drzewa zawiera sie w całości w prawym poddrzewie - wynikiem jest średnica prawego poddrzewa
- średnica całego drzewa zaczyna się w lewym, a kończy w prawym poddrzewie - wynikiem jest wysokośc lewego poddrzewa + wysokość prawego poddrzewa + 1 (czyli długośc ścieżki idącej "z samego dołu" lewego poddrzewa do "samego dołu" prawedo poddrzewa.
0
hmmm wiem o co chodzi z algorytmem tylko nie bardzo wiem jak zakodzić to, wiem że puszcza się dfs'a w dowolnym wierzchołku np. x, potem puszczamy dfs'a w najodleglejszym wierzchołku np. y (nwm jak wyznaczyć najodleglejszy wierzchołek), potem w y znowu puszczamy dfs'a i najodleglejszym wierzchołkiem jest np. z, i wynik jest różnicą z-y
0
hmmm wiem o co chodzi z algorytmem tylko nie bardzo wiem jak zakodzić to, wiem że puszcza się dfs'a w dowolnym wierzchołku np. x, potem puszczamy dfs'a w najodleglejszym wierzchołku np. y (nwm jak wyznaczyć najodleglejszy wierzchołek), potem w y znowu puszczamy dfs'a i najodleglejszym wierzchołkiem jest np. z, i wynik jest różnicą z-y
To co podałeś to cieżko nazwać algorytmem na średnicę (pewnie chodziło Ci o to co wkleił Sarrus, ale to trochę inaczej działa). Ale popatrz na algorytm który podałem, nie ma żadnego DFSa ani wyznaczania najodleglejszego wierzchołka - prosta funkcja rekurencyjna do zapisania w trzech linijkach.
0
spk postaram się to zrobić :)