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. static int znajdzLisc(ref Drzewo dane) {
  2.   for (int i = 0; i < dane.Count; i++) {
  3.     if (dane[i].Count == 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. static void usunPolaczenie(List<int> dane, int y) {
  2.   for (int i = 0; i < dane.Count; i++) {
  3.     if (dane[i] == y) {
  4.       dane.RemoveAt(i);
  5.       return;
  6.     }
  7.   }
  8. }

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

  1. static void dodajPolaczenie(ref Drzewo dane, int x, int y) {
  2.   dane[x].Add(y);
  3.   dane[y].Add(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. static int[] kodujPrufer(ref Drzewo dane) {
  2.   int[] kod = new int[dane.Count - 2];
  3.   for (int i = 0; i < dane.Count - 2; i++) {
  4.     int minIndeks = znajdzLisc(ref 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. static int pierwszyNiewystepujacy(int[] kod, int dl, List<int> lista) {
  2.   for (int i = 0; i < lista.Count; 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. static Drzewo dekodujPrufer(int[] kod, int n) {
  2.   Drzewo dane = new Drzewo();
  3.   List<int> lista = new List<int>();
  4.   for (int i = 0; i < n + 2; i++) {
  5.     dane.Add(new List<int>());
  6.     lista.Add(i);
  7.   }
  8.   for (int c = 0; c < n; c++) {
  9.     int wybrany = pierwszyNiewystepujacy(kod, n - c, lista);
  10.     usunPolaczenie(lista, wybrany);
  11.     dodajPolaczenie(ref dane, wybrany, kod[c]);
  12.   }
  13.   dodajPolaczenie(ref 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. static void Main(string[] args) {
  2.   Drzewo dane = new Drzewo();
  3.   int n, x, y;
  4.   Console.Write("Podaj rozmiar drzewa:\n n = ");
  5.   n = Convert.ToInt32(Console.ReadLine());
  6.   for (int i = 0; i < n; i++)
  7.     dane.Add(new List<int>());
  8.   for (int i = 0; i < n - 1; i++) {
  9.     string[] data = Console.ReadLine().Split(' ');
  10.     x = Convert.ToInt32(data[0]);
  11.     y = Convert.ToInt32(data[1]);
  12.     dane[x].Add(y);
  13.     dane[y].Add(x);
  14.   }
  16.   int[] kod = kodujPrufer(ref dane);
  17.   Console.WriteLine("Zakodowano jako:");
  18.   for (int i = 0; i < n - 2; i++) {
  19.     Console.Write("{0} ", kod[i]);
  20.   }
  22.   Console.WriteLine("\n\nOdczytano drzewo:");
  23.   Drzewo wynik = dekodujPrufer(kod, n - 2);
  24.   for (int i = 0; i < wynik.Count; i++) {
  25.     Console.Write("{0}: ", i);
  26.     for (int j = 0; j < wynik[i].Count; j++) {
  27.       Console.Write("{0} ", wynik[i][j]);
  28.     }
  29.     Console.WriteLine();
  30.   }
  31.   Console.ReadKey();
  32. }