Kod Prüfera – kod pozwalający na zapisywanie drzewa (w rozumieniu teorii grafów) w formie skompresowanego ciągu (bez wypisywania całego zbioru krawędzi) długości n-2, gdzie n stanowi liczbę wierzchołków grafu.
Wyznaczanie kodu Prüfera
Algorytm wyznaczania kodu Prüfera na podstawie opisu drzewa.
Z danego drzewa o zbiorze wierzchołków opisanym jako {1,2,...,n} prowadzi do kodu Prüfera stanowiącego n-2 wyrazowy ciąg liczb ze zbioru {1,2,...,n}.
Jeśli w drzewie jest więcej niż jedna krawędź, szukamy w drzewie wierzchołka stopnia jeden o jak najniższym numerze ze zbioru {1,2,...,n} nazwijmy go v. Znajdujemy jedynego sąsiada tego wierzchołka, nazwijmy go w.
Do ciągu wyjściowego dopisujemy w, usuwamy krawędź {v,w}
Jeśli w drzewie została więcej niż jedna krawędź to przejść ponownie do punktu pierwszego. W przeciwnym wypadku, zapisany dotychczas ciąg jest ciągiem wyjściowym.
Uwaga: Łatwo zaobserwować, że kod Prüfera można zapisać tylko dla drzew o liczbie wierzchołków większej od 2.
Wyznaczanie drzewa z kodu Prüfera
Algorytm wyznaczania opisu grafu na podstawie kodu Prüfera.
Z danego kodu Prüfera stanowiącego n-2 wyrazowy ciąg liczb (a1,a2,...,an-2) ze zbioru {1,2,...,n} prowadzi do opisu drzewa o zbiorze wierzchołków {1,2,...,n} z kodem Prüfera (a1,a2,...,an-2).
Tworzymy dwie listy L1=(a1,a2,...,an-2), L2={1,2,...,n}. Drzewo zaczynamy tworzyć od grafu o wierzchołkach {1,2,...,n} i wyłącznie trywialnych składowych (pusty zbiór krawędzi). Wyznaczmy sobie liczbę c:=1.
Wyznaczamy w L2 najmniejszą wartość, która nie występuje w liście L1 nazwijmy ją i.
Dodajemy do drzewa krawędź {i,ac}. Z listy L1, usuwamy ac. Z listy L2, usuwamy element i.
Jeśli L1 jest niepuste to definiujemy c:=c+1 i wracamy do punktu 2. W przeciwnym wypadku L2 zawiera jeszcze dwa elementy, nazwijmy je l1 i l2. Do zbioru krawędzi drzewa dodajemy krawędź {l1,l2} i kończymy działanie algorytmu.
