План алгоритмы на деревьях Центр дерева Наивный алгоритм

СТАБИЛЬНОЕ ДЕРЕВО, ДЛИННЫЙ И КРАТЧАЙШИЕ ПУТИ, ПЛАНИРОВАНИИ ЛЕНТЫ

ПЛАН

1. 
   Алгоритмы на деревьях
   
2. 
   Центр дерева
   
3. 
   Наивный алгоритм
   

Алгоритмы на деревьях

Диаметр дерева (англ. 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]