Участник:Masha

Алгоритм декодирования кодa Прюфера

В массиве вершин исходного дерева [math]V[/math] найдём вершину [math]v_{min}[/math] с минимальным номером, не содержащуюся в массиве с кодом Прюфера [math]P[/math], т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина [math]p_1[/math] была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {[math]p_1[/math], [math]v_{min}[/math]}, добавим его в список ребер. Удалим первый элемент из массива [math]Р[/math], а вершину [math]v_{min}[/math] - из массива [math]V[/math] т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив [math]P[/math] не станет пустым. В конце работы алгоритма в массиве [math]V[/math] останутся две вершины, составляющие последнее ребро дерева (это следует из построения).

Реализация

# P - код Прюфера
# V - вершины
function buildTree(P, V):
   while not P.empty():
      u = P[0]
      v = min(x [math]\in[/math] V: P.count(x) == 0)
      G.push({u, v})
      P.erase(0)
      V.erase(indexOf(v))
   G.push({v[0], v[1]})
   return G