Я реализовал алгоритм Прима, чтобы найти остовное дерево минимального веса моего графа, и это работает нормально.
Теперь я хотел бы выбрать «лучшую» голову в связующем дереве. Под «лучшим» я подразумеваю более сбалансированный заголовок, например, если я буду отображать дерево в пользовательском интерфейсе treeView. Я уверен, что для этого существует множество алгоритмов, но я не знаю, как назвать проблему!
Одним из критериев, который вы можете использовать, является среднее расстояние от узла до всех остальных узлов. Выберите узел с минимальным средним расстоянием. Вы также можете попробовать среднее квадратное расстояние и т. Д.
Ну, есть splay trees и AVL Trees, которые делают то, о чем вы просите, но они ограничены максимум двумя дочерними элементами на узел. Вы можете попробовать изменить их. Проблема может быть Form a tree which is as wide as possible.
Вы можете использовать «самый внутренний» узел, максимизируя минимальное расстояние до листа. Для его вычисления, я думаю, может работать следующий алгоритм (я не проверял):
S = set of all leaves of the tree
foreach node in S: mark(node)
repeat:
# at each iteration, S is the set of all nodes at
# a given min distance to a leave
# initially this distance is 0, then 1, etc.
S' = empty set
foreach node in S:
parent = parent(node)
if !marked(parent): S' += parent; mark(parent)
if S' is empty then S contains all innermost nodes, we are done
S = S' and continue
