Изменения

Перейти к: навигация, поиск

Участник:Masha

56 байт убрано, 11:44, 29 декабря 2020
Алгоритм декодирования кодов Прюфера
== Алгоритм декодирования кодов кодa Прюфера ==
Пусть есть массив <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> останется две вершины, составляющих последнее ребро дерева.
P.erase(0)
V.erase(indexOf(x))
'''if''' P.count(u) == 0:
V.push(u)
G.push({v[0], v[1]})
'''return''' G
Анонимный участник

Навигация