Минимум максимальных расстояний от любого узла до всех остальных узлов данного Дерева
Для дерева с 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)