49
правок
Изменения
добавлен алгоритм декодирования
== Пример построения кода Прюфера ==
[[Файл: Prufer.png|500px]]
== Алгоритм декодирования кодa Прюфера ==
В массиве вершин исходного дерева <tex>V</tex> найдём вершину <tex>v_{min}</tex> с минимальным номером, не содержащуюся в массиве с кодом Прюфера <tex>P</tex>, т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина <tex>p_1</tex> была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {<tex>p_1</tex>, <tex>v_{min}</tex>}, добавим его в список ребер. Удалим первый элемент из массива <tex>Р</tex>, а вершину <tex>v_{min}</tex> - из массива <tex>V</tex> т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив <tex>P</tex> не станет пустым. В конце работы алгоритма в массиве <tex>V</tex> останутся две вершины, составляющие последнее ребро дерева (это следует из построения).
=== Реализация ===
# P - код Прюфера
# V - вершины
'''function''' buildTree(P, V):
'''while'' '''not'' P.empty():
u = P[0]
v = min(x '''<tex>\in</tex>''' V: P.count(x) == 0)
G.push({u, v})
P.erase(0)
V.erase(indexOf(v))
G.push({v[0], v[1]})
'''return''' G
== Пример декодирования кода Прюфера ==
