http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=93.185.28.157&*Викиконспекты - Вклад участника [ru]2026-04-30T15:09:24ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Masha&diff=75821Участник:Masha2020-12-29T08:44:23Z<p>93.185.28.157: /* Алгоритм декодирования кодов Прюфера */</p>
<hr />
<div>== Алгоритм декодирования кодa Прюфера ==<br />
Пусть есть массив <tex>P = {p_1, ..., p_{n - 2}}</tex> - код Прюфера какого-то дерева и массив вершин дерева <tex>V</tex>. Для получения дерева по коду Прюфера необходимо выполнять следующие действия, пока массив <tex>P</tex> не станет пустым. В массиве <tex>V</tex> найти вершину <tex>v_{min}</tex> с минимальным номером, не содержащуюся в массиве <tex>P</tex>. Добавить ребро {<tex>p_1</tex>, <tex>v_{min}</tex>} в дерево, удалить найденные вершины из соответствующих массивов. В конце работы алгоритма в массиве <tex>V</tex> останется две вершины, составляющих последнее ребро дерева.<br />
<br />
=== Реализация ===<br />
<br />
'''function''' buildTree(P, V):<br />
'''while'' '''not'' P.empty():<br />
u = P[0]<br />
v = min(x '''<tex>\in</tex>''' V: P.count(x) == 0)<br />
G.push({u, v})<br />
P.erase(0)<br />
V.erase(indexOf(x))<br />
G.push({v[0], v[1]})<br />
'''return''' G</div>93.185.28.157