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.
Linki zewnętrzne
Kategoria:Teoria grafów