Strona główna » Algorytmy » Artykuły » Kod Prüfera
 

Kod Prüfera

https://mattomatti.com/a0196

Opis

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

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.

Przykład

Przykładowe drzewo

W celu zakodowanie powyższego drzewo kolejno należy wybierać:

LiśćSąsiadKod Prüfera
011
321, 2
411, 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.

Odkodowanie

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.

Przykład

Przykładowe drzewo

W celu rozkodowania kodu Prüfera 1, 2, 1 tworzymy listę {0, 1, 2, 3, 4} i kolejno wybieramy:

Kod PrüferaListaxy
1, 2, 10, 1, 2, 3, 401
2, 11, 2, 3, 432
11, 2, 421
-1, 414

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.

Implementacja

Przechowywanie drzewa

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.

C++C#
Python
  1. def znajdzLisc(dane):
  2.   for i in range(len(dane)):
  3.     if len(dane[i]) == 1:
  4.       return i
  5.   return -1

Funkcja usunPolaczenie() usuwa z listy dane wartość y. Trzeba ją wywołać dwa razy, aby usunąć krawędź całkowicie!

C++C#
Python
  1. def usunPolaczenie(dane, y):
  2.   dane.remove(y)
  3.   return dane

Z kolei funkcja dodajPolaczenie() dodaje nową krawędź do drzewa:

C++C#
Python
  1. def dodajPolaczenie(dane, x, y):
  2.   dane[x].append(y)
  3.   dane[y].append(x)
  4.   return dane

Kodowanie

Do kodowania drzewa napisana została funkcja kodujPrufer(), która na podstawie przekazanego drzewa zwraca tablicę wartości będących kodem Prüfera.

C++C#
Python
  1. def kodujPrufer(dane):
  2.   kod = [None] * (len(dane) - 2)
  3.   for i in range(len(dane) - 2):
  4.     minIndeks = znajdzLisc(dane)
  5.     kod[i] = dane[minIndeks][0]
  6.     dane[minIndeks] = usunPolaczenie(dane[minIndeks], kod[i])
  7.     dane[kod[i]] = usunPolaczenie(dane[kod[i]], minIndeks)
  8.   return kod

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.

Odkodowanie

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ść.

C++C#
Python
  1. def pierwszyNiewystepujacy(kod, lista):
  2.   for i in range(len(lista)):
  3.     ok = True
  4.     for el in kod:
  5.       if el == lista[i]:
  6.         ok = False
  7.         break
  8.     if (ok): return lista[i]
  9.   return -1

Po napisaniu powyższej funkcji można przejść do napisania funkcji dekodujPrufer(), która na podstawie podanego kodu wygeneruje drzewo.

C++C#
Python
  1. def dekodujPrufer(kod):
  2.   n = len(kod) + 2
  3.   dane = [[] for i in range(n)]
  4.   lista = list(range(n))
  5.   for c in range(n - 2):
  6.     wybrany = pierwszyNiewystepujacy(kod, lista)
  7.     lista = usunPolaczenie(lista, wybrany)
  8.     dane = dodajPolaczenie(dane, wybrany, kod[c])
  9.   dane = dodajPolaczenie(dane, lista[0], lista[1])
  10.   return dane

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.

Testowanie funkcji

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.

C++C#
Python
  1. n = int(input("Podaj rozmiar drzewa:\n n = "))
  2. dane = [[] for i in range(n)]
  3. for i in range(n - 1):
  4.   para = [int(x) for x in input().split()]
  5.   dane[para[0]].append(para[1])
  6.   dane[para[1]].append(para[0])
  8. kod = kodujPrufer(dane)
  9. print("Zakodowano jako:")
  10. for el in kod:
  11.   print(el, end=' ')
  13. print("\n\nOdczytano drzewo:")
  14. wynik = dekodujPrufer(kod)
  15. for i in range(len(wynik)):
  16.   print(i, end=': ')
  17.   for el in wynik[i]:
  18.     print(el, end=' ')
  19.   print()