Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями.
Алгоритм построения кода Прюфера
На вход подается список ребер. Выбирается лист дерева с наименьшим номером, затем он удаляется из дерева, и к коду Прюфера добавляется номер вершины, которая была связана с этим листом. Эта процедура повторяется n-2 раза. В конце концов, в дереве останется только 2 вершины, и алгоритм на этом завершается. Номера оставшихся двух вершин в код не записываются. Таким образом, код Прюфера для заданного дерева – это последовательность из n-2 чисел, где каждое число – номер вершины, связанной с наименьшим на тот момент листом – то есть это число в отрезке [1,n].
Исходное дерево
Код Прюфера: 1
Код Прюфера: 1 5
Код Прюфера: 1 5 2
Код Прюфера: 1 5 2 6
Код Прюфера: 1 5 2 6 6
Код Прюфера: 1 5 2 6 6 2
Код Прюфера: 1 5 2 6 6 2 1
Код Прюфера: 1 5 2 6 6 2 3