Kod Prüfera to kod, który pozwala na zapisanie dowolnego drzewa w postaci skompresowanego ciągu. Po rozkodowaniu otrzymuje się dokładnie ten sam graf, który został zakodowany. Ciąg składa się z n-2 wartości, gdzie n to ilość węzłów w grafie. Drzewo musi mieć węzły ponumerowane kolejnymi liczbami np. od 0 do n - 1.
Kodowanie drzewa polega na: wybraniu węzła, który jest liściem o najmniejszym, przypisanym numerze. Następnie należy do ciągu dopisać numer jego jedynego sąsiada, a jego samego usunąć. Proces ten należy powtarzać tak długo, aż zostaną dwa wierzchołki, które pomija się w zapisie ciągu. Uzyskany kod powinien składać się z n-2 wartości.
W celu zakodowanie powyższego drzewo kolejno należy wybierać:
Liść | Sąsiad | Kod Prüfera |
---|---|---|
0 | 1 | 1 |
3 | 2 | 1, 2 |
4 | 1 | 1, 2, 1 |
Pozostały dwa ostatnie węzły, a więc algorytm został zakończony. W tym przypadku kod Prüfera to 1, 2, 1.
Zakodowane drzewo niewiele mówi wprost o krawędziach grafu. W celu rozkodowania należy utworzyć sobie listę liczb od 1 do p + 2, gdzie p to długość kodu Prüfera. Jak można zauważyć p + 2 = n. Następnie należy wybrać z tej listy pierwszy element x, który nie występuje w kodzie oraz pierwszy element z kodu Prüfera y, a następnie na grafie utworzyć krawędź (x, y) i usunąć x z listy oraz pierwszy element z kodu. Na koniec na liście zostaną dwie wartości tj. ostatnia para wierzchołków do połączenia.
W celu rozkodowania kodu Prüfera 1, 2, 1 tworzymy listę {0, 1, 2, 3, 4} i kolejno wybieramy:
Kod Prüfera | Lista | x | y |
---|---|---|---|
1, 2, 1 | 0, 1, 2, 3, 4 | 0 | 1 |
2, 1 | 1, 2, 3, 4 | 3 | 2 |
1 | 1, 2, 4 | 2 | 1 |
- | 1, 4 | 1 | 4 |
Z kodu Prüfera odczytane zostały kolejno krawędzie: {(0, 1), (3, 2), (2, 1), (1, 4)} czyli wszystkie krawędzie grafu pokazanego wyżej.
Drzewo będzie przechowywane jako lista list, gdzie na i-tej liście będą zapisani sąsiedzi i-tego wierzchołka. Każda krawędź (i, j) ma zapis w dwóch miejscach w drzewie: i-ta lista zawiera j, a j-ta wierzchołek i. Należy o tym pamiętać podczas modyfikowania drzewa. Poniżej zostały krótki opisane funkcje do modyfikowania drzewa.
Funkcja znajdzLisc() wyszukuje w drzewie liść o najmniejszym indeksie i go zwraca. Korzystamy tu z faktu, że liść ma tylko jednego sąsiada.
Funkcja usunPolaczenie() usuwa z listy dane wartość y. Trzeba ją wywołać dwa razy, aby usunąć krawędź całkowicie!
Z kolei funkcja dodajPolaczenie() dodaje nową krawędź do drzewa:
Do kodowania drzewa napisana została funkcja kodujPrufer(), która na podstawie przekazanego drzewa zwraca tablicę wartości będących kodem Prüfera.
Najpierw tworzona jest tablica do zapisu kodu, a następnie dopóki jest więcej niż dwa wierzchołki to: wyszukujemy odpowiedni liść, dopisujemy do kodu i usuwamy całkowicie krawędź z drzewa. Na koniec zwracamy obliczony kod.
Do rozkodowania drzewa została napisana dodatkowa funkcja pierwszyNiewystepujacy(), która szuka pierwszej wartości z lista, która nie występuje w tablicy kod. Funkcja zwraca znalezioną wartość.
Po napisaniu powyższej funkcji można przejść do napisania funkcji dekodujPrufer(), która na podstawie podanego kodu wygeneruje drzewo.
Najpierw tworzona jest lista wartości od 0 do n (docelowej ilości węzłów w grafie). Następnie dla każdej wartości z kodu wyszukiwana jest powiązana wartość z lista i na podstawie znalezionej pary tworzone jest nowe połącznie. Na koniec dopisywane jest ostatnie połączenie z pozostałych na liście dwóch ostatnich wierzchołków i zwracane jest odkodowane drzewo.
Poniższy fragment kodu wpierw wczytuje drzewo tj. wpierw ilość wierzchołków n, a następnie w kolejnych n-1 linijkach pary połączonych wierzchołków. Następnie drzewo jest kodowane, a wynik zostaje wypisany na ekran. Potem kod jest odkodowany, a zwrócone drzewo wypisane.