49
правок
Изменения
Новая страница: «== Алгоритм декодирования кодов Прюфера == Пусть есть массив <tex>P = {p_1, ..., p_{n - 2}}</tex> - код Прю…»
== Алгоритм декодирования кодов Прюфера ==
Пусть есть массив <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> останется две вершины, составляющих последнее ребро дерева.
=== Реализация ===
'''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(x))
'''if''' P.count(u) == 0:
V.push(u)
G.push({v[0], v[1]})
'''return''' G
Пусть есть массив <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> останется две вершины, составляющих последнее ребро дерева.
=== Реализация ===
'''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(x))
'''if''' P.count(u) == 0:
V.push(u)
G.push({v[0], v[1]})
'''return''' G
