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.

  1. int znajdzLisc(const drzewo &dane) {
  2.   for (int i = 0; i < dane.size(); i++) {
  3.     if (dane[i].size() == 1) {
  4.       return i;
  5.     }
  6.   }
  7.   return -1;
  8. }

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

  1. void usunPolaczenie(vector<int> &dane, int y) {
  2.   for (int i = 0; i < dane.size(); i++) {
  3.     if (dane[i] == y) {
  4.       dane.erase(dane.begin() + i);
  5.       return;
  6.     }
  7.   }
  8. }

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

  1. void dodajPolaczenie(drzewo &dane, int x, int y) {
  2.   dane[x].push_back(y);
  3.   dane[y].push_back(x);
  4. }

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.

  1. int* kodujPrufer(drzewo &dane) {
  2.   int * kod = new int[dane.size() - 2];
  3.   for (int i = 0; i < dane.size() - 2; i++) {
  4.     int minIndeks = znajdzLisc(dane);
  5.     kod[i] = dane[minIndeks][0];
  6.     usunPolaczenie(dane[minIndeks], kod[i]);
  7.     usunPolaczenie(dane[kod[i]], minIndeks);
  8.   }
  9.   return kod;
  10. }

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

  1. int pierwszyNiewystepujacy(int * kod, int dl, vector<int> lista) {
  2.   for (int i = 0; i < lista.size(); i++) {
  3.     bool ok = true;
  4.     for (int j = 0; j < dl; j++) {
  5.       if (kod[j] == lista[i]) {
  6.         ok = false;
  7.         break;
  8.       }
  9.     }
  10.     if (ok) return lista[i];
  11.   }
  12.   return -1;
  13. }

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

  1. drzewo dekodujPrufer(int * kod, int n) {
  2.   drzewo dane;
  3.   vector<int> lista;
  4.   for (int i = 0; i < n + 2; i++) {
  5.     dane.push_back(vector<int>());
  6.     lista.push_back(i);
  7.   }
  8.   for (int c = 0; c < n; c++) {
  9.     int wybrany = pierwszyNiewystepujacy(kod, n - c, lista);
  10.     usunPolaczenie(lista, wybrany);
  11.     dodajPolaczenie(dane, wybrany, kod[c]);
  12.   }
  13.   dodajPolaczenie(dane, lista[0], lista[1]);
  14.   return dane;
  15. }

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.

  1. int main () {
  2.   drzewo dane;
  3.   int n, x, y;
  4.   cout << "Podaj rozmiar drzewa:\n n = ";
  5.   cin >> n;
  6.   for (int i = 0; i < n; i++)
  7.     dane.push_back(vector<int>());
  8.   for (int i = 0; i < n - 1; i++) {
  9.     cin >> x >> y;
  10.     dane[x].push_back(y);
  11.     dane[y].push_back(x);
  12.   }
  14.   int * kod = kodujPrufer(dane);
  15.   cout << "Zakodowano jako:\n";
  16.   for (int i = 0; i < n - 2; i++) {
  17.     cout << kod[i] << " ";
  18.   }
  20.   cout << "\n\nOdczytano drzewo:\n";
  21.   drzewo wynik = dekodujPrufer(kod, n - 2);
  22.   for (int i = 0; i < wynik.size(); i++) {
  23.     cout << i << ": ";
  24.     for (int j = 0; j < wynik[i].size(); j++) {
  25.       cout << wynik[i][j] << " ";
  26.     }
  27.     cout << endl;
  28.   }
  29.   system("pause");
  30.   return 0;
  31. }