СТАБИЛЬНОЕ ДЕРЕВО, ДЛИННЫЙ И КРАТЧАЙШИЕ ПУТИ, ПЛАНИРОВАНИИ ЛЕНТЫ
ПЛАН
Алгоритмы на деревьях
Центр дерева
Наивный алгоритм
Алгоритмы на деревьях
Диаметр дерева (англ. diameter of a tree) — максимальная длина (в рёбрах) кратчайшего пути в дереве между любыми двумя вершинами. Пусть дан граф G=⟨V,E⟩G=⟨V,E⟩. Тогда диаметром dd называется maxu,v∈Vdist(v,u)maxu,v∈Vdist(v,u), где distdist — кратчайшее расстояние между вершинами.
Возьмём любую вершину v∈Vv∈V и найдём расстояния до всех других вершин. d[i]=dist(v,i)d[i]=dist(v,i)
Возьмём вершину u∈Vu∈V такую, что d[u]⩾d[t]d[u]⩾d[t] для любого tt. Снова найдём расстояние от uu до всех остальных вершин. Самое большое расстояние — диаметр дерева.
Расстояние до остальных вершин будем искать алгоритмом BFSBFS.
//граф g представлен списком смежности
int diameterTree(list> g):
v = u = w = 0
d = bfs(g, v)
for i = 0, i < n, i++
if d[i] > d[u]
u = i
bfs(g, u)
for i = 0, i < n, i++
if d[i] > d[w]
w = i
return d[w]
Do'stlaringiz bilan baham: |