Минимум максимальных расстояний от любого узла до всех остальных узлов данного Дерева

Опубликовано: 19 Сентября, 2022

Для дерева с N вершинами и N-1 ребрами, представленными двумерным массивом edge[] , задача состоит в том, чтобы найти минимальное значение среди максимальных расстояний от любого узла до всех других узлов дерева.

Примеры:

Input: N = 4, edges[] = { {1, 2}, {2, 3}, {2, 4} } 
Output: 1
Explanation: The Tree looks like the following.
                       2
                   /   |  
                1    3   4
Maximum distance from house number 1 to any other node is 2.
Maximum distance from house number 2 to any other node is 1.
Maximum distance from house number 3 to any other node is 2.
Maximum distance from house number 4 to any other node is 2.
The minimum among these is 1.

Input: N = 10, edges[] = { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} }
Output: 5

Подход: Эту проблему можно решить с помощью поиска в глубину, основанного на следующей идее:

For each node find the farthest node and the distance to that node. Then find the minimum among those values.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Создайте массив расстояний (скажем, d[] ), где d[i] хранит максимальное расстояние до всех других узлов от i -го узла.
  • Для каждого узла, присутствующего в дереве, рассмотрим каждый из них как источник один за другим:
    • Отметьте расстояние источника от источника как ноль.
    • Найдите максимальное расстояние всех остальных узлов от источника.
  • Найдите минимальное значение среди этих максимальных расстояний.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ