Участник:Masha

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

Пусть есть массив [math]P = {p_1, ..., p_{n - 2}}[/math] - код Прюфера какого-то дерева и массив вершин дерева [math]V[/math]. Для получения дерева по коду Прюфера необходимо выполнять следующие действия, пока массив [math]P[/math] не станет пустым. В массиве [math]V[/math] найти вершину [math]v_{min}[/math] с минимальным номером, не содержащуюся в массиве [math]P[/math]. Добавить ребро {[math]p_1[/math], [math]v_{min}[/math]} в дерево, удалить найденные вершины из соответствующих массивов. В конце работы алгоритма в массиве [math]V[/math] останется две вершины, составляющих последнее ребро дерева.

Реализация

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(x))
      if P.count(u) == 0:
         V.push(u)
   G.push({v[0], v[1]})
   return G