Блог пользователя SEFI2

Центр взвешенного дерева
Автор SEFI2, 10 лет назад, По-русски

Всем привет!

Недавно читал о нахождении центра простого дерева:

Центр дерева — это вершина(вершины) на середине самого длинного пути в дереве. И она находится так:

Берем любую вершину X и находим самую отдаленную вершину от нее, пусть это вершина будет Y, и от Y тоже находим самую отделенную вершину Z. Вершины Y — Z окажутся самыми отдаленными вершинами в графе. Очевидно, если этот путь нечетной длинны то центром дерева будет всегда одна вершина, а иначе две.

Решая задачи на эту тему столкнулся с задачей на нахождение центра во взвешенном графе. Сам путь нахожу правильно, а центр найти затрудняюсь.

Можете подсказать как можно решить?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Решение выглядит в точности также — два раза находим самую удаленную вершину. Нашли таким образом самый длинный путь. Пусть его длина L, идём от одного из концов пути ко второму пока расстояние от старта D(p[i]) не превышает L / 2. Пусть D(p[x]) <= L / 2 а D(p[x + 1]) > L / 2. Здесь надо уточнить что считать центром, и выбрать лучшую вершину(вершины, если D(p[x]) == L — D(p[x + 1])) или точку на ребре между вершинами p[x] и p[x + 1].

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо большое !! — Попробую это написать..

    И еще : Вот часть кода где я нахожу центр,

    path — Путь от Y до Z

    Dist — Расстояние от Y до path[i]

    Можете объяснить, почему так неправильно? 

    for (int i = 0; path.size() > i ; i++)
{
        LeftDist = Dist[ path[i] ];
        RightDist = L - Dist[ path[i] ] ;
        
        if( max(LeftDist,RightDist) < ansDist)
        {
              ansDist = max(LeftDist,RightDist) ;
              ansV = path[i];
        }

}
    → Ответить