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

Question

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

Я хочу найти единственный узел в графе, который при использовании в качестве корневого узла создает максимально короткую высоту дерева,Я придумал, как выполнить обход в глубину, используя каждый узел в качестве корня, и отследить самую короткую из увиденных высот.Есть ли более быстрый способ сделать это?

Answer 1

Это вопрос классических алгоритмов. То, что вы ищете, называется центром дерева, и это можно найти с помощью простого итеративного алгоритма. На этот вопрос есть отличный ответ, объясняющий, как это сделать.

Надеюсь, это поможет!