Вот некоторый рабочий код O (N).В этом примере я использую график {0: [1,2,3], 1: [4,5], 2: [6]}
Я кодировал это для шутки.Для приведенного ниже графика он обнаруживает, что центром является узел 0, значение P [i] которого равно 9. Отображение из i-> P [i] равно {0: 9, 1: 10, 2: 12, 3: 14,4: 15, 5: 15, 6: 17}
nodes={0:[1,2,3],1:[4,5],2:[6]}
PB={}
NB={}
def below(i):
if i not in nodes:
PB[i]=0
NB[i]=1
return 0,1
tot_nodes_below=0
tot_paths_below=0
for node in nodes[i]:
paths_below,nodes_below=below(node)
tot_nodes_below+=nodes_below
tot_paths_below+=paths_below
tot_paths_below+=tot_nodes_below
tot_nodes_below+=1
PB[i]=tot_paths_below
NB[i]=tot_nodes_below
return tot_paths_below,tot_nodes_below
P={0:below(0)[0]}
def fill_P(i):
for node in nodes[i]:
P[node]=P[i]+7-2*NB[node] #7 is the number of nodes
if node in nodes:
fill_P(node)
fill_P(0)
_min=min(P.values())
answers=[k for k in P if P[k]==_min]
print answers
"[0]"
Объяснение: Этот код O (N) (я думаю, правильно?)
В основном узлы = dict, который показывает каждого родителяузел, соединяющийся с его дочерними узлами.
Пусть T [i] будет "деревом i".Я определяю это как поддерево, начиная с узла i.(например, T [2] = 2: 6, в то время как T [0] - это целое дерево, T [1] будет 1: [4,5].)
теперь NB [i] - это числоузлов в T [i].
NB = {0: 7, 1: 3, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1}
PB [i] - сумма расстояний узлов от i в пределах T [i].(поэтому PB [i] в основном будет P [i], за исключением того, что мы смотрим только на T [i] вместо T [0].
PB = {0: 9, 1: 2, 2: 1, 3: 0, 4: 0, 5: 0, 6: 0}
См. PB [0] = 9, поскольку в T [0] идет 9 путей, идущих к 0. PB [6] = 0как NB [0] = 1 и т. д.
Таким образом, чтобы фактически построить PB и NB, нам нужна рекурсивная функция O (N) «ниже (i)».
ниже (i) начинается скорневой узел и проходит по каждому поддереву T [i]. Для каждого поддерева он обрабатывает NB [i] и PB [i]. Обратите внимание, что базовый случай рекурсии тривиален, если у узла нет дочернего узла, PB[i] = 0 и NB [i] = 1.
Чтобы определить PB [i] и NB [i] для узла, который имеет дочерние узлы, мы используем рекурсивную формулу. Пусть узел i имеет дочерний элементузлы x1..xj, затем NB [i] = 1 + сумма (NB [x]).
Существует аналогичная рекурсивная формула для расчета PB [i].
PB [i] = SUM (PB [x]) + NB [i] причина, по которой мы добавляем NB [i], состоит в том, что каждый узел ниже должен пройти дополнительное расстояние 1, чтобы добраться от поддерева T [x] до узла i.
Как только наша функция ниже (я) имеет всплНа основании NB и PB, мы можем использовать эти два результата, чтобы выяснить, что P.
fill_P (i) использует NB и PB, чтобы сделать это.
Идея состоит в том, что P [i] будетбыть близким к значению P [j], если узлы i и j находятся рядом друг с другом.
Фактически, давайте посмотрим, сможем ли мы вычислить P [1], используя NB [1], PB [1] иP [0].
получается P [1] = P [0] + 7-2 * NB [1] (нам даже не нужно было использовать результаты от PB, однако нам нужно было PB дляполучить начальное значение P [0]).Чтобы понять, почему эта формула верна, подумайте, почему P [1] не равно P [0].Это помогает иметь изображение дерева.Давайте разделим дерево на две части, удалив узел 1. Теперь это дает левую сторону дерева (которая не включает в себя узел 0) и правую сторону дерева, которая включает в себя узел 0).обратите внимание, что левая часть дерева - это просто T [1], и у нас есть результаты NB [1] для этого.P [1] - это то же самое, что и P [0], за исключением всех путей из узлов в T [1], расстояние перемещения на 1 меньше.Все пути от узлов, не входящих в T [1], проходят 1 дальше (через узел 0, чтобы добраться до узла 1).Количество путей просто NB [1] и 7-NB [1] соответственно.Таким образом, мы имеем P [1] = P [0] + (7-NB [1]) - NB [1], что дает требуемую формулу.
Теперь у нас есть правильные значения P для P [0]и P [1].Мы можем вычислить значения любого потомка узла 1 или узла 0. fill_P просто проходит через каждый из дочерних узлов, применяя эту формулу, и у нас остается результат P. Мы просто перебираем P, чтобы найти минимум, и это наш результат..
Надеюсь, теперь это имеет смысл, ура.