Projektowanie algorytmow i struktura danych

Generalnie mo

że być trochę błędów ale

zgrubsza je poprawi

łem, skanowalem od strony 12

Przyk

ład. Dane n = l oraz z = 1000. Wylosowano następujące liczby: 15, 8, 155,

27, 310, 911, 544. Zawartość tablicy a po wykonaniu procedury generacja(n, z, a):

2.1.2. Wyznaczanie najmniejszego elementu tablicy

Przeglądanie informacji zapisanej w tablicy jednowymiarowej w celu znalezi

nią elementu o najmniejszej wartości jest operacją o złożoności liniowej i zaws.
dotyczy całej długości tablicy. Operacja ta może być rozszerzona o wyprowadzan
informacji o miejscu w tablicy (czyli o indeksie), w którym znajduje się eleme

Algorytm wyznaczania najmniejszego elementu tablicy

Dane: n - długość tablicy, a - tablica o długości n.

W y ni k. Wartość najmniejszego elementu tablicy a.

Metoda: Niech x oznacza najmniejszy element tablicy. Przyjmij początkowo,
pierwszy element tablicy jest poszukiwanym najmniejszym elementem. Następ
dla każdego / od 2 do n porównuj a{i\ z x. Jeśli a[i] jest mniejsze od x, to popi
wartość x. Złożoność: O(ń}.

Implementacja

const nmax = 100;
type ind = L.nmax;

t = array[ind] of integer;

function min(n:integer; var art
var i:integer; x:integer; begin

x:=a[ll;
for i:—2 to n do

if a[i] < x then x:=a[i];

min:=x end; { min }

i n t e g e r ;

Przykład. Po wywołaniu funkcji .y:=min(w, d) dla danych z poprzedniego przykł;
du zmienna y będzie miała wartość 8.

2.1.3. Sortowanie tablicy

Sortowanie informacji występuje bardzo często jako element bardziej rozbudo-

wanych zadań. Opracowano wiele różnych metod sortowania tablicy o złożoności
obliczeniowej od O(n

) do O(nlogn). Opis kilku najważniejszych można znaleźć

w książce [7]. Metodę wykorzystaną w algorytmie sortowania tablicy zastosujemy
również do sortowania listy jednokierunkowej.

Algorytm sortowania tablicy

Dane: n - długość tablicy, a - tablica o długości n.
Wynik: a - posortowana tablica.
Metoda: Wykorzystamy metodę sortowania ciągów zwaną prostym wybieraniem.
W tablicy początkowo nie posortowanej stopniowo powstaje część posortowana
(lewa, czyli o indeksach począwszy od 1) oraz zmniejsza się część nie posortowa-
na. Niech / będzie indeksem początkowego elementu nie posortowanej części ta-
blicy. Dla każdego i' o d l do n - l znajdź najlepszy element (najmniejszy, jeśli
sortujemy rosnąco) w nie posortowanej części tablicy, zamień go z elementem a[/].
Złożoność: O(n

Implementacja

c o n s t n m a x = 1 0 0 ; t y p e
i n d = l.. n m a x ;

t = a r r a y [ i n d ] o f i n t e g e r ; { a }

p r o c e d u r e s o r t ( n : i n t e g e r ; v a r a : t ) ;
v a r i , j , k : i n t e g e r ; n a j : i n t e g e r ; b e g i n

fo r i:=l t o n - 1 d o

b e g i n

naj:=a[i]; k:=i; for
j:=i + 1 to n do if
a[j] > naj then

begin naj:=a[j]; k:=j; end; { popraw }

if i o k then

end
;

begin
a[k] :=a[i]; a[i]
:=naj; end; end; {
i } { sort }

{ zamie

ń }

2.1.4. Obliczanie wartości sumy elementów tablicy

Jest to prosta operacja polegająca na stopniowym obliczaniu wyniku przez do-

dawanie wartości  kolejnego  elementu  tablicy do wartości sumy  obliczonej  w  po-
przednim  kroku  algorytmu.  Ważna  jest  właściwa  inicjalizacja  obliczenia,  czyli
przypisanie wynikowi wartości początkowej równej zero.  Zauważmy, że w przy-
padku obliczania iloczynu elementów tablicy wartością początkową wyniku byłaby
liczba 1.

Algorytm obliczania wartości sumy elementów tablicy jednowymiarowej

Dane: n - długość tablicy, a - tablica o długości n.

Wynik: s - suma elementów tablicy.

Metoda: Niech s oznacza sumę elementów tablicy.
1. Przygotuj s, czyli podstaw zero do s.
2. Przeglądaj tablicę od pierwszego do ostatniego elementu i wartość kolejnego

elementu dodawaj do poprzednio obliczonej wartości sumy s.

Złożoność: O(ri).

Implementacja

c o nst n m a x = 10 0;
t y p e i n d = L. n m a x ;

t = a r r a y[ i n d ] of i nt e g er ; { a }

f u n c t i o n s u m a ( n : i n t e g e r ; v a r a : t ) : i n t e g e r ;
v a r i : i n t e g e r ; s : i n t e g e r ; b e g i n

s : = 0 ;

f o r i : = l t o n d o s : = s + a [ i ] ;

s u m a : = s; end;

{ suma }

2.1.5. Wyszukiwanie informacji w tablicy

Ważną operacją słownikową jest wyszukiwanie informacji w strukturze danych

czyli operacja member. Jeżeli struktura jest bardzo duża i operacja jest wykonywa-
na często, to optymalizacja wyszukiwania ma istotny wpływ na jakość całego pro
jektu. Istotną cechą dobrego wyszukiwania jest zakończenie działania, gdy poszu-
kiwana informacja zostanie znaleziona. Przeglądanie struktury jednowymiarowe
(np. tablicy) od początku do końca ma miejsce tylko wówczas, gdy nie ma poszu
kiwanej informacji w tej strukturze lub gdy zostanie ona znaleziona w ostatnin
elemencie. Odmianą operacji member jest nie tylko odpowiadanie na pytanie „cz;
jest?", ale również „gdzie jest?" lub „ile razy występuje?".

Algorytm wyszukiwania informacji w tablicy jednowymiarowej

Dane: x - informacja (np. liczba całkowita), n - długość tablicy, a - tablica.

Wynik: Informacja o tym, czy x jest elementem tablicy.

Metoda: Dla wartości indeksów tablicy od l do co najwyżej n porównaj wartość
kolejnego elementu tablicy z wartością x. Jeśli x zostanie znalezione w tablicy, to
zakończ wyszukiwanie.

Złożoność: O(n).

Implementacja

const nmax = 100;
type ind = 1.. nmax;

t = array[ind] of integer;

function member(x: integer; n: integer; var a: t):
Boolean; var i: integer; jest: Boolean; begin

jest: =false;
i: =l;

w h i l e (i < = n) a n d n ot j est d o

i f a [ i ] = x t h e n j e s t : = t r u e e l s e i : = i + 1 ;

m e m b er : = j es t ;

end; { member }

2. 2. Tablice dwuwymiarowe i tablice rekordów

2. 2. 1. Generacja grafu losowego G(n, p)

Graf G jest określany jako para G = (V, E), gdzie F jest zbiorem wierzchołków a

E- zbiorem krawędzi grafu.  Zwykle  przyjmuje  się  F= {l, 2,...,  n} i  wtedy  zbiór
E zawiera pewną liczbę par wierzchołków (i, j). Wierzchołki  grafu, między  który-
mi  istnieje  krawędź,  nazywamy  przyległymi.  Jeżeli  krawędzie  mają  wyróżniony
kierunek, to graf  nazywamy  grafem  skierowanym  (ang.  directed  graph  lub  krótko
digraph). Będziemy rozważać przede wszystkim grafy proste, czyli nie skierowane,
bez krawędzi wielokrotnych oraz bez tzw. pętli własnych (i, i).

Macierz przyległości grafu jest macierzą kwadratową o elementach O i 1 ,

zawierającą informację o krawędziach grafu. Jeśli element tej macierzy o
indeksach i, j ma wartość l, to w grafie istnieje krawędź (i, f). Największą liczbę
krawędzi na n wierzchołkach, czyli \E\ = n(n - l)/2, ma graf K

, nazywany grafem

pełnym (ang. complete graph).

Graf losowy jest to graf, którego krawędzie zostały wylosowane zgodnie z okre-

ślonym modelem. Jednym ze znanych modeli grafów losowych jest model G(n, p),

w którym rozważa się niezależnie każdą krawędź grafu pełnego K

i z prawdopo-

dobieństwem p wybiera ją do grafu losowego G o n wierzchołkach. Wartość ocze-
kiwana liczby krawędzi grafu G jest równa pn(n - l)/2.

Reprezentacją macierzy przyległości grafu G w strukturze danych jest tablica

kwadratowa A o elementach typu logicznego („false" i „true") lub typu całkowite-
go (O i l, odpowiednio). Jeśli w grafie G istnieje krawędź (i,j), to element i-tego
wiersza oraz j-tej kolumny w A ma wartość „true", a także j-tego wiersza oraz i-tej
kolumny, ponieważ G jest grafem prostym. Z tego samego względu na przekątnej
głównej tablicy A powinny się znajdować wartości „false".

Algorytm generacji grafu losowego G = G(«, p)

Dane: n - liczba wierzchołków grafu, p - prawdopodobieństwo krawędziowe.
Wynik: A - macierz przyległości grafu G reprezentowana w tablicy kwadratowej.
Metoda: Każda krawędź ze zbioru o liczności n(n - l)/2 ma być niezależnie wy-
brana do grafu G (na n wierzchołkach) z prawdopodobieństwem p.

1. Przygotuj tablicę A (wystarczy przygotować jej główną przekątną).
2. Dla każdego elementu tablicy A o indeksach i, j (l <= i <=j <= n):

wylosuj liczbę z przedziału (O, 1),

b. jeśli ta liczba jest nie większa niż p, to dodaj krawędź (i, j) do grafu G,
c.

uzupełnij informację o krawędzi (j, i) w tablicy A.

Złożoność: O(n

Implementacja

Boolean

Rys. 2.2. Tablica kwadratowa o elementach typu logicznego do reprezentacji grafu

const nmax = 100;
type ind = l..nmax;

t2 = array[ind,ind] of Boolean; { A }

procedure Gnp(n:integer; p:real; var A:t2);
var i,j:integer; x:Boolean; begin

for i:=l to n do A[i,i]:=false; { przek

ątna główna }

for i:=l to n - 1 do for j:= i + 1 to n do begin

x:= random <= p; A[i,j]:=x;
A[j,i]:=x; end; end; { Gnp }

Przykład. Wylosowano następujący graf przy n = 4, p = 0.5

G: l

2.2.2. Generacja grafu losowego G(n, K)

Drugim modelem grafów losowych, wykorzystywanym w projektowaniu inży-

nierskim, jest model G(n, k), w którym dana jest liczba wierzchołków grafu i liczba
jego krawędzi. Jest to model sekwencyjny, czyli do grafu, który nie ma jeszcze ani
jednej krawędzi, dodaje się pierwszą wylosowaną krawędź, potem drugą i tak da-
lej, aż do uzyskania grafu o k krawędziach. Aby poprawnie wygenerować graf
losowy G = G(n, k), należy spełnić w każdym kroku algorytmu warunek jednako-
wego prawdopodobieństwa wylosowania każdej jeszcze nie wybranej krawędzi.

Zwykle generujemy więcej niż jeden graf losowy, musimy więc zwrócić uwagę,

że operacja przygotowania tablicy krawędzi E (czyli init) jest wykonywana tylko
raz - przed generacją pierwszego grafu.

Algorytm generacji grafu losowego G = G(n, k)

Dane: n - liczba wierzchołków, k - liczba krawędzi grafu, E - tablica wszystkich
krawędzi na n wierzchołkach.

Wynik: Graf G jest reprezentowany w tablicy E (k elementów o najwyższych in-
deksach, czyli z prawej części tablicy).

Metoda:  Początkowo  w  tablicy  E  znajdują  się  wszystkie  krawędzie  na  n  wierz-
chołkach  w  dowolnym  porządku.  Niech  h  oznacza  ostatni  (czyli  największy)  in-
deks w roboczej części tablicy E, czyli tej części, z której będziemy  losować  kra-
wędzie grafu G.

1. Podstaw h równe n (n - l)/2.

2. Powtórz k razy następujące operacje:

losuj z jednakowym prawdopodobieństwem jeden z indeksów tablicy E
z przedziału [l, h],

b. zamień wylosowany element z elementem E[h] oraz

zmniejsz h o 1.

Złożoność: O(n

Implementacja

Rys. 2.4. Tablica rekordów o dwóch polach typu całkowitego do generacji grafu G = G(n, k)

const nmax = 100; kmax = nmax*(nmax - 1) div 2;
type ind = 1.nmax;

t = array[ind] of integer;
r = record a,b:integer end;
tl = array[indl] of r;

{ E }

procedure init(n:integer; var E:t1; var total:integer) ;
var i,j,h:integer; begin

h:=0;

{ przygotowanie indeksu }

f o r i : = l t o n - 1 d o for

j : =i + 1 to n do b e g i n

h: = h + 1;

{ powiększenie indeksu }

w i t h E[ h] d o b e g i n a: = i; b: = j e n d ; { krawędź }

e n d ;

t o t a l : = h ;

{ liczba wszystkich krawędzi, n(n - l ) / 2 }

en d; { init }

p r o c e d u r e G n k ( n , k , t o t a l : i n t e g e r ; v a r E : t 1 ) ;
v a r i , h , z : i n t e g e r ; x : r ;
b e g i n

h : = t o t a l ; f o r i : = l
t o k d o b e g i n

z : = r a n d o m( h ) + 1 ; { l o s o w a n i e i n d e k s u t a b l i c y E }
x: = E [ z]; E [ z ] : = E [ h ] ; E[ h]:= x;

{ za miana }

h:=h - 1; { zmniejszenie przedziału losowania } e n d ;

end; { Gnk }

2.2.3. Transformacja E-->A reprezentacji grafu

Jeżeli po wygenerowaniu grafu losowego G = G(n, k) w tablicy E wykonujemy

dalsze operacje, do których realizacji wygodniejszą strukturą danych jest tablica
kwadratowa, to należy przekształcić pierwotną reprezentację grafu G w reprezenta-
cję docelową. W miarę poznawania nowych struktur danych należy ćwiczyć się
w umiejętności przekształcania informacji z jednej struktury danych w inną.

Algorytm transformacji E —>A reprezentacji grafu

Dane: n - liczba wierzchołków, k - liczba krawędzi, E - reprezentacja grafu loso-
wego G = G(n, k).
Wynik: A - reprezentacja grafu G w tablicy kwadratowej.
Metoda:
1.  Oblicz total = n(n - l)/2 - największy indeks tablicy E.
2.  Przygotuj tablicę A (wszystkie elementy).
3.  Wybieraj informację o krawędziach grafu G = G(n, k) z tablicy E (k elemen

tów o indeksach od total do total - k + 1) i przepisuj do tablicy A.

Złożoność: O(n

Rys. 2.5. Struktury danych do transformacji E —> A reprezentacji grafu G = G(n, k)

const nmax = 100; kmax = nmax*(nmax-1) div 2;
type ind = 1..nmax; ind1 = l..kmax; r =
record a,b:integer end;

tl = array[ind1] of r;

{ E }

t2 = array[ind,ind] of Boolean;

{ A }

procedure transEA(n,k:integer; var E:tl; var A:t2);
var i,j,h,total:integer; begin

total:=n*(n - 1) div 2;
for i:=l to n do

for j:=l to n do A[i,j]:=false;

for h:=total downto total - k + 1 do { kraw

ędzie }

begin

with E[h] do begin i:=a; j:=b end;
A[i,j]:=true; A[j,i]:=true; end; end; {
transEA }

2.3. Zbiory i tablice rekordów zawierających zbiory

2.3.1. Tworzenie zbioru losowych liczb całkowitych

Zbiory są strukturą stosowaną w przypadku przetwarzania danych z ograniczo-

nego zakresu wartości, np. liczb całkowitych z przedziału  od  l do 256.  W  języku
Pascal  elementami  zbiorów  mogą  być  tylko  zmienne  okrojonego  typu  prostego.
Operacjami  standardowymi  są:  suma,  różnica  i  iloczyn  zbiorów  (o  symbolach
operacji odpowiednio +, -, *) oraz relacja należenia do zbioru (słowo  kluczowe
in). Wyrażenia typu zbiorowego umieszcza się w nawiasach kwadratowych. Dal-
sze szczegóły dotyczące typu zbiorowego w języku Pascal znajdują się w książce
[3]. Poniższy algorytm tworzy zbiór w (o liczności n) liczb  całkowitych  z prze-
działu od l do z.

Algorytm tworzenia zbioru losowych liczb całkowitych

Dane: n - liczność zbioru, z - zakres losowania.
Wynik: w - zbiór losowych liczb całkowitych z przedziału [l, z].

Metoda:

1. Przygotuj zbiór.
2. Powtórz n razy losowanie liczby z przedziału od l do z oraz dodawanie jej do

zbioru.

Złożoność: O(n).

Implementacja

const nmax = 100; type
elem = 1.nmax;

zbiór = set of elem;

procedure konsr(n,z:integer; var w:zbior);
var i:integer; x:elem; begin w: = [];

for i:=l to n do

begin

x:= random(z) + 1; w:=w +
[x] end; end; { konstr }

2.3.2. Wyprowadzanie zawartości zbioru

Wyprowadzanie zawartości zbioru można zaprojektować jako sprawdzanie ca-

łego zakresu wartości jego elementów zgodnie ze zdefiniowanym  typem. Lepsze
rozwiązanie przedstawia podany niżej algorytm, w którym zastosowano przegląda-
nie  zbioru  w  i  odejmowanie  od  niego  kolejnych  znalezionych  elementów.  W  im-
plementacji  tego  algorytmu  zbiór  w  jest  przekazywany  do  podprogramu  „przez
wartość", a więc można zmieniać jego zawartość, nie niszcząc wartości zmiennej
globalnej.

Algorytm wyprowadzania zawartości zbioru

Dane: w - zbiór liczb całkowitych, first - liczba całkowita.
Wynik: Wyprowadzenie do pliku wyjściowego (wydrukowanie) elementów zbioru
nie mniejszych niż first.
Metoda: Dopóki zbiór w nie jest pusty, wyprowadzaj kolejne elementy zbioru,
odejmując każdorazowo ten element od zbioru.

Złożoność: O(n).

Implementacja

c o n s t n m a x = 1 0 0 ; t y p e
e l e m = l. . n m a x ;

z b i ó r = s e t o f e l e m ;

p r o c e d u r e d r u k z b i o r ( f i r s t : i n t e g e r ; w : z b i o r ) ;
v a r x : e l e m ; b e g i n

x : = f i r s t ; w hile w
< > [] do b e g i n

if x i n w t he n

b e g i n

w r i t e ( o u t , x : 3 , ' , ' ) ;
w : = w - [x] e n d ;

x : = x + 1 ; e n d ; e n d;

{ dr u k z b i or }

2.3.3. Transformacja A-->S reprezentacji grafu

W przypadku wykonywania niektórych operacji na grafach, np. rozdzielania je-

go reprezentacji według składowych grafu, stosuje się strukturę tablicową, która

zawiera informację o wierzchołkach przyległych, czyli sąsiadach kolejnych wierz-
chołków grafu. Jeśli graf G został wygenerowany w tablicy kwadratowej A, to
transformację jego reprezentacji w tablicę sąsiadów S przedstawia poniższy algo-
rytm.

Algorytm transformacji A -> S reprezentacji grafu

Dane: n - liczba wierzchołków grafu, A - macierz przyległości grafu G.
Wynik: S - reprezentacja grafu G w tablicy sąsiadów.

Metoda:

1. Przygotuj tablicę sąsiadów S.
2. Dla każdego elementu A[i, j], l <= i < j <= n , sprawdź, czy wierzchołki i,

j
grafu są przyległe. Jeśli tak, to aktualizuj elementy S[i] oraz S[j] w następujący
sposób:
a. dodaj j do zbioru sąsiadów wierzchołka i,
b. dodaj i do zbioru sąsiadów wierzchołka j
c. powiększ o l odpowiednie liczniki l.

Złożoność: O(n

Implementacja

Rys. 2.6. Struktury danych w implementacji algorytmu transformacji A—> S reprezentacji

grafu G

const nmax = 100;
type ind = l..nmax;

elem = 1..nmax;

zbior = set of elem;

rS = record w:zbior;

l:integer; end;

t2 = array[ind,ind] of Boolean; { A }
tS = array[ind] of rS;

{ S }

procedure transAS(n:integer; var A:t2; var S

var i,j:integer;

begin

for i:=l to n do with S[i] do begin w:=[];
for i:=l to n - 1 do for j:=i + 1 to n do
if A[i,j] then begin

with S[i] do begin w:=w + [j]; 1:=1 + with
S[j] do begin w:=w + [i]; 1:=1 + end; end; {
transAS }

2.4. Przetwarzanie informacji o grafach w strukturach tablicowych

2.4.1. Testowanie spójności grafu

Odwiedzanie wszystkich wierzchołków grafu jest podstawą większości algo

rytmów. Dwie główne metody przeglądania grafu  to: metoda BFS (Breadth  Fir.
Search), czyli przeglądania wszerz, i metoda DFS (Depth First Search), czyli prze
glądania  w  głąb.  W  metodzie  BFS  przegląda  się  systematycznie  wszystkich  m
odwiedzonych sąsiadów kolejnego wierzchołka. W metodzie DFS odwiedza się
sąsiada danego wierzchołka, następnie jego nie odwiedzonego sąsiada i tak dale
aż  do  odwiedzenia  wszystkich  wierzchołków,  do  których  można  dojść  z
danego

1;
1;

e n d;
e n d;

t S ) ;

l:=0; e n d;

Przykład. Reprezentacja grafu G w tablicy S

wierzchołka. Jeśli graf nie jest spójny, to aby odwiedzić wszystkie jego wierzchoł-
ki, należy wielokrotnie wybierać wierzchołki początkowe. Szczegółowy opis tych
metod znajduje się w książce [5].

Algorytm testowania spójności grafu przegląda wierzchołki, rozpoczynając tyl-

ko raz - od danego wierzchołka. Jeśli odwiedzi wszystkie wierzchołki, to graf jest
spójny (czyli ma jedną składową), w przeciwnym przypadku graf nie jest spójny.

Rozszerzeniami algorytmu testowania spójności są: zliczanie składowych spój-

ności oraz rozdzielanie reprezentacji grafu według jego składowych.

Algorytm testowania spójności grafu

Dane: n - liczba wierzchołków, A - macierz przyległości grafu G.

Wynik: Informacja o tym, czy graf G jest spójny.

Metoda: Wykorzystuje się przeglądanie grafu rekurencyjną metodą DFS.

1.  Odwiedzamy wierzchołek v = 1.
2.  Szukamy wierzchołka j - pierwszego nie odwiedzonego sąsiada wierzchołka v.
3.  Odwiedzamy wierzchołek j.
4.  Podobnie jak z wierzchołkiem v postępujemy z wierzchołkiem j.
5.  Jeżeli odwiedzimy w ten sposób wszystkie wierzchołki grafu, to graf jest

spójny.

Złożoność: O(n

Implementacja

Rys. 2.8. Struktury danych zastosowane w implementacji algorytmu testowania spójności grafu:
tablica kwadratowa A oraz wektor x, w którym przechowuje się informację o tym, które wierzchołki

grafu zostały odwiedzone

const nmax = 100;
type ind = 1.nmax;

t2 = array[ind,ind] of Boolean; { A } t3 =
array[ind] of Boolean; { x } procedure
DFS(n,v:integer; var A:t2; var x:t3); var
j:integer; begin

for j : =1 to n do

if A[v,j] and not x[j] then

begin

x[j]:=true; DFS(n, j, A,
x) end; end; { DFS }

function spójny(n:integer; var A:t2):Boolean;

var i:integer; x:t3; b:Boolean;

begin

for i:=l to n do x[i]:=false;
x[1]:=true;
DFS(n, 1, A, x);

b:=true;

i: =1 ;

while (i <= n) and b do

begin b:=x[i]; i:=i + 1; end;

spójny:=b;

end; { spójny }

2.4.2. Wyznaczanie liczby trójkątów w grafie

Liczba cykli o danej długości na różnych zbiorach krawędzi jest często poszu

kiwaną własnością grafu. Przegląd algorytmów zliczania cykli rozpoczynamy od
najłatwiejszego z nich, czyli od wyznaczania liczby cykli o długości równej 3.

Algorytm wyznaczania liczby trójkątów w grafie

Dane: n - liczba wierzchołków, A - macierz przyległości grafu G.

Wynik: x - liczba trójkątów w grafie G.
Metoda: Początkowo liczba trójkątów jest równa zeru. Przeglądaj krawędzie graft
i dla każdej z nich sprawdź, czy jej końce mają wspólnego sąsiada. Jeśli tak, te
zwiększ liczbę trójkątów w grafie o jeden.

Złożoność: O(n

Implementacja

co nst n ma x = 100;
ty p e i n d = l.. n m a x ;

t 2 = a r r a y [ i n d , i n d ] o f B o o l e a n ;

{ A }

f u n c t i o n t r i a n g l e s ( n : i n t e g e r ; v a r A : t 2 ) : i n t e g e r ;
v a r i , j , h : i n t e g e r ; x : i n t e g e r ;

begin

x:=0;

f or i : = l t o n - 2

d o f or j: = i + 1 t o n
d o

i f A [ i , j ] t h e n

i f A [ i , h ] a n d A [ j, h ]

t h e n x : = x + 1 ;
tr i a n g l e s : = x

e n d; { tria n gl es }

2.4.3. Wyznaczanie liczby czworokątów w grafie

Przedstawiamy dwa algorytmy zliczania cykli o długości równej 4. Pierwszy

z nich jest naturalnym rozszerzeniem algorytmu zliczania cykli o długości równej 3
i dlatego jego złożoność jest O(n

). W drugim algorytmie wykorzystano inny po-

mysł - zmniejszono złożoność obliczeniową do O(n

Algorytm wyznaczania liczby czworokątów w grafie

Dane: n - liczba wierzchołków, A - macierz przyległości grafu G.
Wynik: x - liczba czworokątów (cykli o długości 4) w grafie G.
Metoda:

1. Podstaw x równe zeru.
2. Dla każdej krawędzi (i, j) grafu G:

a. sprawdź, czy wśród wierzchołków od j + l do n jest taki wierzchołek k,

który jest sąsiadem wierzchołka ;', oraz czy wśród wierzchołków od i do n
jest taki czwarty wierzchołek h, różny od trzech pozostałych, który jest
jednocześnie sąsiadem wierzchołka k i wierzchołka j;

b. jeśli tak, to zwiększ x o l.

Złożoność: O(n\

Implementacja

c onst n ma x = 100; t y p e
i n d = l.. n m a x ;

t 2 = arr a y[in d, i n d] of B o ol ea n; { A }

function cykl4(n:integer; var A:t2):integer;

{ Miros

ław Kupczyk, Inf III, 1996 }

var i,j,k,h,x:integer; begin x: =0 ; if n >= 4 then

for i:= 1 to n - 3 do

for j:=i + 1 to n - 1 do

if A[i,j] then

for k:=j + 1 to n do

if A[i,k] then

for h:=i + 1 to n do

if (h <> j) and (h O k) then

if A[j,h] and A[k,h] then x:=x + 1;

cykl4:=x; end; { cykl4 }

Drugi algorytm wyznaczania liczby czworokątów w grafie

Dane: n - liczba wierzchołków grafu, A - macierz przyległości grafu G.
Wynik: x - liczba cykli o długości 4.

Metoda: Podstaw x równe zeru. Dla każdej pary wierzchołków grafu G oblicz c
liczbę wspólnych sąsiadów. Jeżeli c jest większe od l, to powiększ x o c(c - l)/2
liczbę cykli o długości 4 dla tej pary wierzchołków.
Złożoność: O(n

Implementacja

f u n c t i o n c y k l 4 T F ( n : i n t e g e r ; v a r A : t 2 ) : l o n g i n t ;

{ T o ma sz Fitzer ma nn, EiT Ir., 1998 )

v a r i , j , k : i n t e g e r ; c , x : l o n g i n t ; b e g i n x : = 0 ; if n > = 4
t he n

f o r i: = 1 t o n - l d o fo r

j: = i + l t o n d o b e g i n
c: = 0 ; fo r k: =i + l to n d o

i f A [ i, k ] a n d A [ j, k ] t h e n c : = c + 1 ; i f c

> = 2 t h e n x: = x + c * ( c - 1) di v 2; end;

c y kl 4 T F : = x ; end;

{ cykl4TF }

2.4.4.

Wyznaczanie liczby cykli o danej długości

Problem zliczania cykli o dowolnej długości ma złożoność wykładniczą Do

rozwiązywania  tego  problemu  proponujemy  algorytm  Cycles  (autor  M  Kupczyk,
ulepszenia  K  Zwierzynski,  1998)  W  implementacji  algorytmu  wykorzystano
procedurę  rekurencyjną  OnCycle,  która  jest  realizacją  metody  DFS  przeglądania
grafu, wzbogaconej o elementy metody (Branch and Bound) ograniczania rozmiaru
drzewa  obliczeń  W  tym  przypadku  ograniczanie  to  polega  na  usuwaniu  z  grafu
zbędnych  krawędzi,  czyli  takich,  które  nie  będą  mogły  być  wykorzystane  do  bu-
dowy następnych ścieżek

Podczas wykonywania algorytmu reprezentacja grafu w tablicy A ulega zmia-

nie, więc aby nie zniszczyć pierwotnej informacji o grafie G, tablica ta jest przeka-
zywana do podprogramu Cycles „przez wartość"

Algorytm wykorzystuje następujące struktury danych A - tablicę kwadratową

do  reprezentacji  grafu  oraz  trzy  wektory  o  długości  n  Jeden  z  nich  -  x  o  warto-
ściach typu  logicznego  - przechowuje  (jak  w  realizacji  DFS)  informację  o  tym,
które  wierzchołki  zostały  już  odwiedzone  Dwa  pozostałe  wektory  mają  elementy
typu całkowitego Deg - ciąg stopni  wierzchołków  grafu, m - aktualna ścieżka
w grafie

Algorytm wyznaczania liczby cykli o danej długości

Dane n - liczba wierzchołków grafu, c - długość cyklu, A - macierz przyległosci
grafu G
Wynik h - liczba cykli o długości c w grafie G

Metoda

1 Podstaw h równe O
2 Dla każdego wierzchołka l należacego [l, n - c + 1] wykonaj następujące

operacje
a wybierz i jako pierwszy wierzchołek ścieżki w grafie G,
b wykorzystując metodę przeglądania grafu w głąb (DFS), konstruuj ścieżki

o długości c + l rozpoczynające się od wierzchołka l, nie zawierające
wierzchołków o numerach mniejszych od i,

c jeżeli numer ostatniego wierzchołka ścieżki jest równy numerowi jej
pierwszego wierzchołka, czyli jeżeli został znaleziony nowy cykl o długości c, to
zwiększ h o l Złożoność 0((n-c+ l)!)

Implementacja

Struktury danych przedstawiono na rys 2 9

Boolean

integer

Boolean

Rys. 2.9. Struktury danych wykorzystane w implementacji algorytmu zliczania cykli o danej d ługośi

const nmax = 100;

type ind = l..nmax;

t = array [ind] of integer; { m, Deg }
t2 = array [ind,ind] of Boolean; { A }
tx = array [ind] of Boolean;

{ x }

function Cycles(n, crinteger; A:t2):integer;

var i,j:integer; m,Deg:t; x:tx; h:integer;

procedure OnCycle(d, w, r:integer);
var v,i,j:integer;

begin

if d = c + 1 then

begin if w = m[l] then h:=h + 1 end
else begin

if not x[w] then

begin

if Deg[w] = 1 then

for v:=r to n do
begin

A[w,v]:=false;
A[v,w]:=false end
else begin m[d]:=w;
x[w]:=true;

f o r   v : = r     t o     n   d o
if  A [ w , v ]     t h e n    O n C y c l e( d    +     1 ,    v,   r );  i f
d     =     2   t h e n  b e g i n

i : = m [ 1 ] ;   j : = m [ 2 ] ;   A [ i , j ] : = f a l s e ;
A [   j , i ] : = f a l s e ;   D e g [ i ] : = D e g [ i ]       -
1 ;   D e g [ j]   : = D e g [ j ]     -     1 ;  e n d;    { if   d
}  m [ d ] : = - ! ;   x [ w ] : = f a l s e ;   e n d;    {
else   }  e n d;     {   if   n ot    }  e n d;    {   else
}  end;   {    O n C y cle     }

be gin { C ycles }

h : = 0 ;

if c > = 3 t he n

b e g i n

f o r i: = 1 t o n d o

b e g i n

x [ i ] : = f a l s e ;
m [ i ] : = - 1 ;
D e g [ i ] : = 0 e n d ;

f o r i: = l t o n - 1 d o

f o r j: =i + 1 t o n d o
i f A [ i, j ] t h e n b e g i n

D e g [ i ] : = D e g [ i] + 1 ;
D e g [ j] : = D e g [ j] + 1 ;
e n d ;

f o r i : = l t o n - c + 1 d o O n C y c l e ( 1 , i , i ) ;

e n d;

C y c l e s: = h ; end;

{ Cycles }

3. PLIKI

3.1. Pliki liczb całkowitych

3.1.1. Konstruowanie pliku

Plik jest strukturą danych wykorzystywaną do przechowywania ciągów infor-

macji o nieznanej długości. Nową informację dopisujemy na końcu pliku. Zawar-
tość  pliku  można  pobierać  tylko  od  początku  pliku.  Standardowymi  operacjami
plikowymi  (zrealizowanymi  jako  procedury)  są  w  języku  Pascal:  rewrite(p)
przygotowanie pliku  p  do zapisu,  write(p, x) -  dołączenie x  na  końcu  pliku  p,  n
set(p) - przygotowanie pliku p do odczytu, read(p,  x) - pobranie x z aktualnego
miejsca  w  pliku  p  oraz  close(p)  -  zamknięcie  pliku  p.  Funkcja  standardowa
eof(p) o wartościach logicznych służy do wykrywania sytuacji  końca pliku p (jej
wartoś jest wtedy równa „true").

W implementacji operacji plikowych należy pamiętać o tym, że parametry typ

plikowego zawsze przekazuje się „przez zmienną". Dalsze wiadomości o plikac
sekwencyjnych i o pozostałych operacjach standardowych można znaleźć w książ
kach [3, 7, rozdz.l]. Tutaj przedstawimy najpierw podstawowe operacje na plikac
liczb całkowitych, a następnie wykorzystanie plików w operacjach odsiewani
grafów.

Algorytm konstruowania pliku losowych liczb całkowitych

Dane: n - długość pliku, z - zakres losowania.

Wynik: p - plik losowych liczb całkowitych z przedziału [l, z].

Metoda:

1.  Przygotuj plik p do zapisu.
2.  Powtórz n razy losowanie liczby całkowitej oraz zapisanie tej liczby w pliku f
3.  Zamknij utworzony plik p.
Złożoność: O(n).

Implementacja

type plik = file of integer; procedure
konstr (n, z : integer; var p:plik) ; var i:
integer; x: integer! begin

rewrite(p);

for i:=l to n do

begin x:=random(z) + 1; write(p, x); end;

close(p); end; {

konstr }

3.1.2. Wyprowadzanie pliku

Jeżeli chcemy wyprowadzić informacje zgromadzone w pliku roboczym do

pliku wynikowego, to musimy wykonać poniższą operację.

Algorytm wyprowadzania pliku

Dane: p - plik liczb całkowitych.
Wynik: zawartość pliku p wyprowadzona do pliku wynikowego.
Metoda:
1.  Przygotuj plik p do odczytu.
2.  Przeglądaj plik p do końca i każdy element przepisz do pliku wynikowego.
3.  Zamknij plik p.

Złożoność: O(n), gdzie n jest długością pliku.

Implementacja

t y p e p l i k = f i l e o f i n t e g e r ;

p r o c e d u r e d r u k p l i k ( v a r p : p l i k ; v a r ou t :t e x t ) ;
v a r x : i n t e g e r ;
begi n

b e g i n r e a d ( p , x ) ; w r i t e ( o u t , x ) ; e n d ;

c l o s e ( p ) ; end; { drukplik }

3.1.3. Poszukiwanie informacji w pliku

Operacja member poszukiwania informacji w pliku jest wykonywana podobnie

jak w tablicy jednowymiarowej. Algorytm podany niżej można rozszerzyć o znale-
zienie wszystkich wystąpień danej informacji w pliku.

Algorytm poszukiwania informacji w pliku

Dane:  x  -  liczba  całkowita,  p  -  plik  liczb  całkowitych.
Wynik: Informacja o tym, czy x jest elementem pliku/?.
Metoda:
1.  Przygotuj plik p do odczytu.
2.  Przeglądaj plik p i wartość każdego elementu porównuj z wartością x, dopóki

plik p się nie skończy lub nie zostanie znaleziony element x.

3. Zamknij plik/?.
Złożoność: O(n), gdzie n jest długością pliku.

Implementacja

type plik = file of integer;
function member(x:integer; var p:plik):Boolean;

var i:integer; y:integer; jest:Boolean;

begin

reset(p);
jest:=false;

while not eof(p) and not jest do

begin

read(p, y) ;
if x = y then jest:=true;

end;

close(p);
member:=jest;
end; { member }

3.1.4. Łączenie plików posortowanych

Przegląd metod sortowania plików przedstawiono w książce [7, rozdz. 2].

ograniczymy się do omówienia algorytmu merge łączenia plików posortowan;
w jeden plik posortowany. W implementacji tego algorytmu wykorzystano prc
dury standardowe get(p) i put(p) używane do wymiany informacji między zmi
na buforowąp\ pliku p a tym plikiem (szczegóły w książkach [3, 7]).

Algorytm łączenia plików posortowanych

Dane: f, g - pliki liczb całkowitych posortowane niemalejąco.
Wynik: h - posortowany plik zawierający informację z plików/ g.
Metoda:
1. Przygotuj pliki/ g do odczytu, plik h do zapisu.
2. Przepisuj do pliku h mniejszą liczbę z pliku/lub g oraz pobieraj kolejną lic

z odpowiedniego pliku aż do końca jednego z plików/lub g.

3. Przepisz pozostałą informację z drugiego pliku do pliku h.
4. Zamknij pliki/ g oraz h.
Złożoność: O(n), gdzie n jest łączną długością plików/oraz g.

Implementacja

t y p e p l i k = f i l e o f i n t e g e r ;

p r o c e d u r e m e r g e ( v a r f , g : p l i k ; v a r h :p l i k) ;
v a r b : B o o l e a n ;

b e g i n

reset (f); reset (g); rewrite (h) ;
b:=eof (f) or eof (g)

while not b do

begin

if f ^ < g^

then

begin h^ : =f ^; get(f); b:=eof(f);

else

,__

begin h^ :=g ^; get(g); b:eof(g);

put(h) ;

end;

while not eof (f) do begin h^:=f^; put(h)
while not eof (g) do begin h^:=g^; put(h)

3.2. Pliki grafów. Przesiewanie

3.2.1. Testowanie izomorfizmu

Metody sita lub tzw. przesiewanie są jedną z technik wyodrębniania obiektów o

potrzebnych własnościach ze  zbioru  wszystkich  generowanych  obiektów.  Znanym
przykładem jest algorytm poszukiwania liczb pierwszych metodą sita Eratostenesa.
Warunkiem wykorzystania tych metod do obiektów złożonych, jakimi są grafy,
jest dysponowanie metodą porównywania struktur i  oceny,  czy  dane  dwa  grafy
mają tę samą strukturę,  czyli czy są izomorficzne. Izomorfizm  jest relacją  między
dwoma  grafami.  Dwa  grafy  są  izomorficzne,  jeśli  istnieje  odwzorowanie  zbioru
wierzchołków pierwszego grafu w zbiór wierzchołków drugiego grafu, zachowują-
ce przyległość wierzchołków.

Wiadomo, że w ogólnym przypadku problem testowania izomorfizmu grafów

ma złożoność wykładniczą. Nie zostały określone proste warunki wystarczające
i konieczne do tego, aby dwa grafy były izomorficzne. Jednakże można wymienić
wiele niezmienników grafu (tzw. inwariantów), które można sprawdzić, zanim się
przystąpi do zasadniczego testowania. Są to przede wszystkim:  liczba wierzchoł-
ków,  liczba krawędzi, posortowany  ciąg stopni  wierzchołków,  liczba  składowych
spójności. Jeśli algorytm wyznaczenia wartości niezmiennika (np. liczba cykli
o długości  3)  ma złożoność większą  niż O(n\  to  na  ogół  wykorzystanie  takiego
niezmiennika nie jest celowe.

Istnieje wiele różnych metod rozwiązywania problemu testowania izomorfizmu

(por. rozdz. 11.7 w książce [2]). Jedną z nich jest wyznaczenie ciągu kanoniczne-
go, który jednoznacznie określa strukturę grafu (por. [4]). Jest to taki ciąg binarny
o długości n(n - l)/2, odpowiadający wyborowi krawędzi grafu (ułożonych w po-
rządku leksykograficznym), którego wartość liczbowa jest największa spośród

end

end;

get(f) end; get(g) end; close(f); close(g); close(h);
end; { merge }

wartości wszystkich możliwych ciągów dla danej struktury. Na przykład, ciąg ka
noniczny grafu G = P

(ścieżka o czterech wierzchołkach) ma postać: ll001i

czyli odpowiada wyborowi krawędzi: (l, 2), (l, 3) oraz (2, 4). Jeżeli ciągi kani
niczne grafów są równe, to grafy są izomorficzne.

Inną metodą jest przeglądanie grafów (np. metodą DFS); jeśli dla każdej

wierzchołka pierwszego grafu znajdziemy odpowiadający mu wierzchołek w dru
gim  grafie,  to  grafy  te  są  izomorficzne.  Oczywiście,  najpierw  trzeba  sprawdzić,
czy grafy  te  mają  jednakową  liczbę  wierzchołków  i  taki  sam  posortowany  ciąg
stopni  wierzchołków.  Tę  metodę  zastosowano  w  algorytmie  iso6  (funkcja
EqualGraph autor: Jędrzej Miądowicz Inf. I r., 1994). Jeżeli chcemy sprawdzić,
czy  grafy  G  L  są  izomorficzne,  to  umieszczamy  każdy  z  nich  w  strukturze
danych typu TGrap i wywołujemy funkcję EqualGraphs(n, G, H).

3.2.2. Transformacja E —> Gr reprezentacji grafu

Jeżeli grafy są generowane w tablicy krawędzi E (np. gdy są to grafy losów

G(n, k)), to aby można było wykorzystać algorytm iso 6 testowania izomorfizm
należy przekształcić reprezentację grafu z tablicy E w rekord typu TGraph (zdef
niowany w module iso6). Rekord ten oprócz reprezentacji macierzy przyległośi
grafu w polu A (tablica kwadratowa o wartościach logicznych) ma jeszcze dw
pola (tablice jednowymiarowe o wartościach całkowitych): Deg - do przechowy
wania ciągu stopni wierzchołków i DegSort - posortowanego ciągu stopni.

Implementacja tego przekształcenia składa się z dwóch operacji:

1. przepisania krawędzi grafu z E do pola A w Gr oraz.
2. wyznaczenia wartości pól Deg i DegSort w Gr z informacji w polu A.
Takie rozwiązanie jest bardziej elastyczne, jeśli uwzględnimy fakt, że grafy k

sowę mogą być generowane w różnych strukturach i wtedy używamy innej proce
dury tylko do przeniesienia informacji o krawędziach grafu do pola A rekordu.

Algorytm transformacji E —> Gr reprezentacji grafu

Dane: n - liczba wierzchołków, k - liczba krawędzi, E - reprezentacja grafu G.

Wynik: Gr - reprezentacja grafu w rekordzie typu TGraph.
Metoda:

1.  Przepisz informację o krawędziach grafu G z tablicy E do pola A rekordu Gr.
2.  Oblicz ciąg stopni wierzchołków grafu G i zapisz go w polach Deg i DegSort.
3.  Posortuj ciąg stopni malejąco (informację zawartą w polu DegSort).
Złożoność: O(n

Implementacja
Struktury danych przedstawiono na rys. 3.1.

Rys. 3.1. Struktury danych w implementacji algorytmu transformacji E -> Gr reprezentacji

grafu G = G(n, k)

const nmax = 100; kmax = nmax*(nmax-1) div 2;
type ind = l..nmax; indl = l..kmax;

r = record a,b:integer end;

{ Gnk }

tl = array[indl] of r;

{ E }

t2 = array [ind,ind] of Boolean;

{ A }

t3 = array [ind] of byte;

TGraph = record A:t2; Deg,DegSort:t3; end;

procedure transEGr(n,k,total:integer; var E:tl;

var Gr:TGraph);

var i, j,h:integer; begin

with Gr do begin

for i:=l to n do for j:=l to n do A[i,j]:=false;
for h:=total downto total - k + 1 do begin

with E[h] do begin i:=a; j:=b; end;
A[i,j]:=true; A[ j,i] :=true; end; end; end; {
transEGr }

procedure jeden(n:integer; var Gr:TGraph);

var i,j,s:integer;

procedure sort(n:integer; var a:t3);

var i,j,k,naj:integer;

begin

for i:=1 to n - 1 do

begin

naj:=a[i]; k:=i; for

j : =i + 1 to n do

if a[j] > naj then begin naj:=a[j]; k:=j;end;

a[k]:=a[i]; a[i]:=naj; end;

end; { sort }

begin { jeden }

with Gr do begin

for i:=l to n do

begin s: =0 ;

f o r j: = l t o n d o i f A [ i,j] t h e n s : = s + 1 ;
D e g [ i ] : = s ; D e g S o r t [ i ] : = s ; e n d ;

s o r t ( n , D e g S o r t ) ; e nd;

en d; { j ede n }

3.2.3. Konstruowanie pliku grafów samodopełniających

Każdemu grafowi G o n wierzchołkach i k krawędziach odpowiada graf G

, n;

zywany dopełnieniem (ang. complement) grafu G, zawierający  te  krawędzie gra:
pełnego, które nie wystąpiły w grafie G. Graf nazywamy samodopełniającym lv
krótko  sc  grafem  (ang.  self-complementary),  jeżeli  jest  izomorficzny  ze  swoi
dopełnieniem.  Liczba  krawędzi  takiego  grafu  jest  równa  n(n  -  l)/4.  Wynika  sfc
warunek  na  liczbę  wierzchołków  n,  który  musi  być  spełniony,  aby  można  by
skonstruować  sc  graf:  reszta  z  dzielenia  liczby  wierzchołków  przez  4  musi  b]
równa O lub l, czyli = s O, l (mod 4).

Trzy najmniejsze sc grafy przedstawiono na rysunku 3.2. W celu skonstruowa

nią wszystkich 10 grafów tej klasy o 8 wierzchołkach lub wszystkich 36 grafów o
wierzchołkach wystarczy powtórzyć odpowiednią liczbę razy następujące
operacji

1. generację grafu losowego G = G(n, k),
2. wyznaczenie G

3. sprawdzenie, czy grafy G i G

są izomorficzne, i jeśli tak, to zapamiętan

jednego z nich w pliku sc grafów.

Niektóre struktury mogą wielokrotnie wystąpić w tym pliku. Następną operacją

może być sprawdzenie:

1.  ile różnych struktur zostało wygenerowanych,
2.  czy uzyskano wszystkie sc grafy o n wierzchołkach, oraz
3.  jaka była liczba wystąpień każdej struktury podczas generacji.
Istnieje również dokładna metoda (G. Ringel, H. Sachs) konstruowania sc  gra-

fów, w której wykorzystuje się kolorowanie krawędzi grafu pełnego K

dwoma

kolorami. W wyniku implementacji tej metody wygenerowano (por. [1]) wszystkie
sc grafy o 12 i 13 wierzchołkach (odpowiednio 720 oraz 5600 grafów).

Rys. 3.2. Trzy najmniejsze sc grafy, n = 4 oraz n = 5

Algorytm konstruowania pliku sc grafów

Dane: n - liczba wierzchołków, n = O, l (mod 4), rep - rozmiar próby.
Wynik: W- plik wygenerowanych sc grafów, g - długość pliku W.
Metoda:
1.  Wyznacz liczbę krawędzi sc grafu k = n*(n - 1) div 4.
2.  Przygotuj plik W do zapisu, tablicę krawędzi E oraz licznik grafów.
3.  Wykonaj rep razy następujące operacje:

a. wygeneruj graf losowy Gl = G(n, k),
b. przepisz G l do rekordu typu TGraph,
c. wyznacz G2 - dopełnienie grafu Gl w rekordzie typu TGraph,
d. jeśli Gl i G2 są izomorficzne, to dopisz Gl do pliku W oraz powiększ o je

den wartość licznika grafów.

4. Zamknij plik W.
Złożoność: zależy od złożoności testowania izomorfizmu grafów.

Implementacja

const nmax = 100; kmax = nmax* (nmax-1) div 2 ;
t yp e i n d = l. . n ma x; i n d 1 = 1. . k ma x;

r = r e c o r d a , b : i n t e g e r e n d ;
t l = a r r a y [ i n d l ] o f r ;

{ E }

t 2 = arr a y[ i n d, i n d ] of B o olea n; { A }
1 3 = a r r a y [ i n d ] of b yt e;

{ Deg, DegS ort }

T G r a p h = r e c or d A :t 2; D e g, D e g S or t :t 3 e n d;
p l i k = f i l e o f T G r a p h ;

procedure complement(n:integer; var Gl, G2:TGraph);
var i,j:integer; { G2 jest dope

łnieniem grafu Gl }

begin

G2:=G1; with
G2 do

for i:=l to n - 1 do

for j:=i + 1 to n do
begin

A[i,j]:=not A[i,j]; A[j,i]:=not A[j,i] end;

end; { complement }

procedure konstr(n,k,rep:integer; var W:plik;

var g:integer);

var i,h,total:integer; E:tl; Gl,G2rTGraph;
begin

rewrite(W); init(n,
E, total);
i:=0;

{ licznik wygenerowanych sc grafów }

for h:=l to rep do

begin

Gnk(n, k, total, E);
transEGr(n, k, total, E, Gl) ;

jeden(n, Gl);

complement(n, Gl, G2);
jeden(n, G2) ;
if EqualGraphs(n, Gl, G2)then

begin i:=i + 1; write(W, G1); end; end;

g:=i; close(W); end; { konstr }

3.2.4. Przesiewanie

Jeżeli po uzyskaniu pliku grafów chcemy utworzyć plik zawierający tylko różi

grafy, tzn. parami nieizomorficzne, to wykonujemy operację przesiewania.

Algorytm przesiewania

Dane: n - liczba wierzchołków, W- plik grafów, g - długość pliku W.

Wynik: Z - plik różnych grafów, sc - długość pliku Z.

Metoda:

l. Przepisz pierwszy graf z pliku W do pliku Z, ustaw licznik elementów pliku Z

2. Pobieraj kolejne grafy z pliku W i każdy z nich porównuj ze wszystkimi gra

fami w pliku Z (operacja member z testowaniem izomorfizmu grafów).

3. Jeśli nie ma takiego grafu w pliku Z, to dopisz ten graf do Z i powiększ o l

licznik elementów pliku Z.

Złożoność: Zależy od długości pliku W oraz od złożoności testowania izomorfizmu
grafów.

Implementacja

t y p e p l i k = f i l e o f T G r a p h ;

p r o c e d u r e p r z e s i e w a n i e ( n , g : i n t e g e r ; v a r W , Z : p l i k ;

v a r s c : i n t e g e r ) ;

var i,j,h:integer; jest:Boolean; Gl, G2:TGraph;
begin

reset(W);
rewrite(Z) ;
read(W, Gl);

{ pierwszy graf z W do Gl }

'write (Z, Gl) ;

{ przepisz Gl do pliku Z }

close(Z) ;
j:=l;

{ aktualna d

ługość pliku Z }

for i:=2 to g do

{ przegl

ądaj plik W }

begin

read(W, Gl); { pobierz kolejny graf z W do Gl }
reset(Z); { przygotuj plik Z do odczytu }
{ porównaj Gl z kolejnymi G2 z pliku Z: }
jest:=false; h:=l;

while (h <= j) and not jest do

begin

read(Z, G2);
if EqualGraphs(n, Gl, G2) then jest:=true

else h:=h + 1;

end;

if not jest then { gdy Gl nie ma w Z, to dopisz }

begin
write (Z, Gl);
j:=j + 1; close
(Z); end;

end; { i }

sc:=j;

{liczba ro

żnych sc grafów w pliku Z }

close(W);

{ zamkniecie pliku W }

end; { przesiewanie }

3.2.5. Generacja grafu losowego G(n,f)

W projektowaniu inżynierskim mamy często do czynienia z grafami, w których

liczba  sąsiadów  każdego  wierzchołka  jest  ograniczona  z  góry  przez  wartość  par
metru f Nazywamy je grafami z ograniczonym stopniem wierzchołków lub krótl
f-grafami.  W  tej  klasie  grafów  wyróżnia  się  maksymalne  f-grafy  (ze  względu  i
liczbę  krawędzi).  Można  je  podzielić  według  wartości  m  -  liczby  wierzchołkó
nienasyconych  (tzn.  o  stopniu  mniejszym  niż  f).  Na  rysunku  3.3  zamieszczeń
wszystkie  maksymalne  2-grafy  o  liczbie  wierzchołków  n  =  4,  5  z  m
wierzchołkami nienasyconymi (m = O, l, 2).

m=0

m= l

m=2

Rys. 3.3. Przykłady maksymalnych/-grafów (f= 2, n =4, 5) z m wierzchołkami nienasyconymi

(w = 0,1,2)

Praktyczne znaczenie mają/grafy, w których 2 </< n - l. Zwykle generujem

losowe/-grafy, wykorzystując model sekwencyjny G(n,f), w którym maksymalny
f-graf powstaje stopniowo z grafu pustego o n wierzchołkach przez losowanie
kollejnych krawędzi i dodawanie ich do grafu. Muszą być przy tym spełnione
następujące warunki:

1. każda krawędź jest losowana z jednakowym prawdopodobieństwem ze

zbioru
wszystkich dostępnych krawędzi,

2. wylosowaną krawędź można dodać do grafu, jeżeli jej wierzchołki mają

stopień mniejszy niż f.

Pierwszy z powyższych warunków jest taki sam jak w modelu G(n, k). Kc

nieczność spełnienia drugiego warunku sprawia, że nie  każdą  wylosowaną  krawęd
można dodać do grafu. Musimy  więc zaznaczyć, które krawędzie  należą do grafi
W implementacji algorytmu generacji grafu G = G(n,J) wykorzystuje się tablicę.
rekordów  o  trzech  polach,  z  których  dwa  przechowują  krawędź,  a  trzecie  (poi
code typu logicznego) służy do odróżniania krawędzi. Na początku generacji graf
wszystkie krawędzie są oznaczone jako „false". Dodanie  krawędzi do grafu wiąż
się  z  podstawieniem  wartości  „true"  do  pola  code.  Po  zakończeniu  generacji  kra
wędzie maksymalnego f-grafu są rozproszone w całej tablicy E.

Algorytm generacji grafu losowego G = G(n, f)

Dane: n - liczba wierzchołków, /- maksymalny stopień wierzchołka, E - tablica
zawierająca wszystkie krawędzie na n wierzchołkach.
Wynik: E - reprezentacja grafu G = G(n, f) w tablicy rekordów.
Metoda: Niech h będzie indeksem końca roboczej części tablicy E.
1.  Przygotuj tablicę E do losowania krawędzi grafu G.
2.  Przygotuj tablicę c, w której przechowuje się ciąg stopni wierzchołków grafu.
3.  Podstaw/z =n(n-l)/2.
4.  Powtarzaj następujące operacje, dopóki h jest dodatnie:

a. losuj z - indeks elementu z przedziału [l, h],
b. jeśli wylosowana krawędź E[z] może być dodana do grafu G, czyli jeśli

stopnie jej wierzchołków są mniejsze niż f to oznacz ją jako dobrą i zaktu
alizuj c,

c. zamień miejscami elementy E[z] i E[h] tablicy E oraz zmniejsz h o 1.

Złożoność: O(n

Implementacja

const nmax = 100; kmax = nmax*(nmax-1) div 2;
type ind = 1..nmax; ind1 = 1..kmax;

rE = record a,b:byte; code:Boolean end;
t = array[ind] of integer;

{ c }

tE = array[ind1] of rE;

{ E }

procedure Gnf(n,f,total:integer; var E:tE; var c:t;

var k:integer);

var i,h,y,z:integer; x:r; begin

for i:=l to n do c[i]:=0;
for i:=l to total do E[i].code:=false;
y:=0;

{ licznik kraw

ędzi }

for h:=total downto 1 do

begin

z:=random(h) + 1;

{ losowanie indeksu )

with E[z] do

{ sprawdzenie )

if (c[a] < f) and (c[b] < f) then

begin

code:=true; y:=y
+ 1; c[a]:=c[a] +
1; c[b]:=c[b] +
1; end;

x:=E[z]; E[z]:=E[h]; E[h]:=x; { zamiana ] end;

k:=y; end; { Gnf }

Grafy, w których wszystkie wierzchołki są nasycone, czyli są stopnia f nazy-
wamy regularnymi. Liczba ich krawędzi jest równa nf/2. Jest to ważna klasa
grafów Do generacji losowych grafów f-regularnych o n wierzchołkach
wystarczy wykorzystać algorytm generacji maksymalnego f-grafu losowego
G = G(n, i odsiewać grafy o liczbie krawędzi k = n f/2.

4. STRUKTURY LISTOWE

4.1. Lista jednokierunkowa

4.1.1. Dopisywanie informacji na początku listy

Lista jest dynamiczną strukturą danych składającą się z elementów tego samego

typu,  podobnie  jak  tablica  i  plik,  ale  jest  tworzona  i  usuwana  z  pamięci  podczas
wykonywania  programu.  Inną  cechą  różniącą  listę  od  tamtych  struktur  jest  możli-
wość  dopisywania  do  niej  nowych  elementów  w  dowolnie  wybranym  miejscu,  bez
potrzeby  przepisywania  informacji.  Każdy  z  elementów  listy  jednokierunkowej
zawiera nie tylko informację  do  przetwarzania,  ale  również  wskazuje  miejsce,
w  którym  znajduje  się  kolejna  informacja.  Aby  mieć  dostęp  do  listy,  wystarczy
znać  wskaźnik  jej  początku,  czyli  głowę  listy.  Najprostszym  algorytmem  dopisy-
wania do listy jest algorytm  dopisywania  nowego  elementu  na początku poprzed-
nio utworzonej listy.

W implementacji tego algorytmu została użyta standardowa procedura języka

Pascal, new(p), która przydziela nowy obszar w pamięci rekordowi reprezentują-
cemu element listy, przy czym zmienna wskaźnikowa p ma wartość adresu począt-
ku tego obszaru w pamięci. Zmienna wskazywana przez zmienną wskaźnikową p
nazywa się/? t (por. [3]).

Algorytm dopisywania informacji na początku listy

Dane: x - informacja (np. liczba całkowita), h - głowa listy. Wynik: h - głowa
listy rozszerzonej o jeden element na początku. Metoda: Wygeneruj nowy
element, wpisz do niego r, przyłącz element do początku listy oraz zaktualizuj h.
Złożoność: 0(1).

Implementacja

type ref = ^elem;

elem = record a:integer; next:ref; end;

procedure push(x:integer; var h:ref);

var p:ref;

begin

new(p);
with p^ do begin a:=x; next:=^h; end;

h:=p end; {

push }

4.1.2. Konstruowanie listy z dopisywaniem na początku

Do sprawdzania poprawności zaprojektowanych algorytmów działających na li-

stach  jednokierunkowych  wykorzystuje  się  algorytm  konstruowania  listy  elemen-
tów  o  wartościach  losowych.  Postąpimy  tu  podobnie  jak  w  przypadku  poprzednio
omawianych struktur danych i utworzymy  listę liczb całkowitych. Metoda  konstru-
owania  listy  jest  jednak  ogólna  i  stosujemy  ją  do  elementów  dowolnego  typu,  np.
grafów  losowych.  Proszę  zwrócić  uwagę,  że  algorytm  konstruowania  listy  z  dopi-
sywaniem  na  początku  odwraca  porządek  wygenerowanego  ciągu,  czyli  pierwszy
element ciągu znajduje się na końcu listy.

Algorytm konstruowania listy z dopisywaniem na początku

Dane: n - długość listy, z - zakres losowania.

Wynik: h - głowa listy.

Metoda: Przygotuj listę, a następnie powtórz n razy losowanie liczby z przedziału
[l, z] i dopisanie jej na początku listy.

Złożoność: O(n).

Implementacja

a next

Rys. 4.1. Lista jednokierunkowa przechowująca liczby całkowite

type ref = ^elem;

elem - record a:integer; next:ref; end;

procedure konstrlista(n,z:integer; var h:ref);
var i: integer; x :integer; begin

h:=nil;

{ przygotuj list

ę }

for i:=l to n do

begin

x:=random{z) + 1;

{ losuj liczb

ę }

push(x, h);

{ dopisz do pocz

ątku listy }

end; end; {

konstrlista }

4.1.3. Wyprowadzanie informacji z listy

Do przeglądania listy nie jest potrzebna informacja o jej długości. Wystarczy

rozpocząć  przeglądanie  od  pierwszego  elementu  i  przesuwać  wskaźnik  na  kolejny
element  dopóki  będzie  on  miał  wartość  różną  od  wskaźnika  pustego  (nil).  W  im-
plementacji  poniższego  algorytmu  wykorzystano  licznik  wyprowadzonych  ele-
mentów listy, aby drukować po 10 elementów w jednej linii wyników.

Algorytm wyprowadzania informacji z listy

Dane: h - głowa listy.

Wynik: Informacja z listy przepisana do pliku wyjściowego out.
Metoda: Przeglądaj listę i przepisuj do pliku wyjściowego informację z kolejnych

elementów listy.
Uwaga: obsługę pliku out zaprojektowano poza tym algorytmem.
Złożoność: O(ń), gdzie n jest długością listy.

Implementacja

type ref = ^elem;

elem = record a:integer; next:ref; end;

procedure druklista(h:ref); var i:integer;
begin

writeln(out, 'lista:');

i:=0; { licznik wydrukowanych elementów listy }
while h O nil do begin

with h^ do

begin

write (out, a: 6); i:=i -f 1; if i mod
10 = 0 then writeln{out); end;

h:=h^.next;

end;

writeln(out); end;

{ druklista }

4.1.4. Poszukiwanie informacji na liście

Operacja member jest analogiczna do tych, które projektowaliśmy dla tablic

i plików, różni się tylko sposobem przeglądania struktury danych.

Algorytm poszukiwania informacji na liście jednokierunkowej

Dane:x- poszukiwana informacja (np. liczba całkowita), h -głowa listy.
Wynik: Informacja o tym, czy x jest na liście h.
Metoda: Przeszukujemy listę, porównując informację w kolejnym elemencie
z wartością x. Operacja kończy się, gdy znajdziemy x albo gdy sprawdzimy ostatni
element listy.

Złożoność: O(n), gdzie n jest długością listy.

Implementacja

type ref = ^elem;

elem = record a:integer; next:ref; end;

function member(x:integer; h:ref):Boolean;
var jest:Boolean; begin

jest:^false;

while (h <> nil) and not jest do

if h^.a = x then jest:=true else h:=h^.next;

member:=jest;

end; { member }

4.1.5. Sortowanie listy z zamianą informacji

Wykorzystamy tę samą metodę sortowania, którą zastosowaliśmy do sortowa-

nia tablic. Jest ona łatwa do zrealizowania, ma jednak tę wadę, że wymaga zamiany
informacji.  W  przypadku  tablic  jest  to  postępowanie  naturalne.  Aby  zmienić  po-
rządek  występowania  elementów  na liście,  można  zmienić  odpowiednie  wskaźniki.
Zachęcamy  do  zaprojektowania  algorytmu  sortowania  listy  z  zamianą  wskaźni-
ków.  Warto  porównać  średnią  złożoność  czasową  tych  dwóch  algorytmów
i  sprawdzić,  jaki  powinien  być  rozmiar  pola  informacyjnego  elementu  listy,  aby
było opłacalne stosowanie algorytmu sortowania z zamianą wskaźników.

Algorytm sortowania listy z zamianą informacji

Dane: h - głowa listy.

Wynik: Posortowana lista o głowie h.

Metoda: Niech h będzie początkiem nie posortowanej części listy. Na początku
sortowania jest to głowa listy. Wykonuj podane niżej operacje, dopóki nie posor-

towana część listy nie jest pusta.

1. Wybierz najlepszy element w nie posortowanej części listy (np. największy).
2. Zamień miejscami tę informację z informacją znajdującą się w elemencie

wskazywanym przez h i przesuń wskaźnik h na następny element listy.

Złożoność: O(n

Implementacja

type ref = ^elem;

elem = record a:integer; next:ref; end;

procedure sortlista(h:ref); { z zamiana informacji }
var p,r;ref; naj:integer; begin

while h <> nil do

begin

naj:=h^.a; r:=h;

{ malej

ąco }

p:=h^.next; { od nast

ępnego do końca listy }

while p O nil do begin

if p^.a > naj then

begin naj:=p^.a; r:=p; end;

p:=p^.next;
end; { p }
if r <> h then

{ zamiana }

begin r^.a:=h^.a; h^.a:=naj end;

h:=h^.next; { skroc nie posortowana cze

ść listy } end;

{ h } end; { sortlista }

4.1.6. Usuwanie pierwszego elementu listy

Jeśli usuwamy informacje z listy, to musimy zwolnić przydzieloną (za pomocą

operacji new(p}} pamięć. Służy do tego standardowa operacja dispose(p). Dobrym
zwyczajem jest podstawianie pustego wskaźnika nil do pola wskaźnikowego ele-
mentu usuwanego z listy przed użyciem operacji dispose.

Algorytm usuwania pierwszego elementu listy

Dane: h - głowa listy.

Wynik: x - informacja z pierwszego elementu danej listy, h - głowa skróconej
listy.

Metoda:

1.  Jeżeli lista nie jest pusta, to wyprowadź informację z pierwszego elementu.
2.  Zapamiętaj początek danej listy i ustaw nowy początek listy.
3.  Zwolnij obszar pamięci zajęty przez pierwszy element danej listy.
Złożoność: O(l).

50 Implementacja

type ref = ^elem;

elem = record aiinteger; next:ref; end;

procedure pop(var h:ref; var x:integer) ; var
p:ref; begin

if h <> nil then

begin

x:=h^.a; p:
=h ;

h : = h ^ . n e x t ;
p ^ . n e x t : = n i l ;
d i s p o s e ( p ) ; e n d ; end;
{ po p }

4.1.7. Dopisywanie elementu na końcu listy

Jeżeli chcemy skonstruować listę zawierającą elementy danego ciągu informacji

w nie zmienionym porządku, to wykorzystujemy algorytm dopisywania elementu
na końcu listy, tradycyjnie nazywany into. W tym przypadku nic wystarczy wskaź-
nik początku listy, ale potrzebny jest również wskaźnik aktualnego końca listy
(ang. sentinel).

Algorytm dopisywania elementu na końcu listy

Dane: x - informacja (np. liczba całkowita), h - głowa listy, s - koniec listy.

Wynik: h, s - głowa i koniec przedłużonej listy.
Metoda:

1. Wygeneruj nowy element, zapisz w nim informację x.
2. Jeśli lista nie była pusta, przyłącz nowy element do końca listy; w przeciwnym

przypadku element ten będzie pierwszym elementem listy.

3. Zaktualizuj s.

Złożoność: O(n), gdzie n jest długością listy.

Implementacja

type ref = ^elem;

elem = record a:integer; next:ref; end;

procedure into(x:integer; var h, s:ref); var
p:ref; begin

new(p);

w i t h   p- ^    d o  b e g i n    a: = x ;     n e xt : = nil;   e n d ; if     h
< >       n i l     t h e n       s ^ . n e x t ; = p      e l s e      h : = p ;   s:  = p ; e n d ;
{   int o   }

4.1.8. Wstawianie informacji na listę posortowaną rosnąco

Jeżeli chcemy połączyć operację tworzenia i sortowania listy, to możemy wyko-

rzystać podany niżej algorytm. W implementacji tego algorytmu zastosowano pro-
cedurę rekurencyjną.

Algorytm wstawiania informacji na listę posortowaną rosnąco

Dane: x - informacja, h - głowa listy posortowanej rosnąco.

Wynik: h - głowa listy posortowanej rosnąco, zawierającej nowy element.

Metoda: Jeśli lista jest pusta lub wartość x jest mniejsza od wartości zapisanej

w aktualnym elemencie listy, to wykonaj operację push', w przeciwnym przypadku
wykonaj operację insert dla kolejnego elementu listy.
Złożoność: O(n), gdzie n jest długością listy.

Implementacja

t y p e r ef = ^ el e m;

e l e m = r e c o r d a : i n t e g e r ; n e x t : r e f ; e nd ;

p r o c e d u r e i n s e r t (

: i n t e g e r ; v a r h : r e f) ;

b e g i n

if ( h = nil) o r ( x < h ^ . a ) t h e n p u s h (x , h )

else insert(x, h^.next)

end; { insert }

4.1.9. Konstruowanie listy grafów

Przedstawiamy algorytm tworzenia listy grafów, gdy na liście są umieszczane

wszystkie wygenerowane grafy losowe G(n, f) o  maksymalnej  liczbie  krawędzi
i dodatkowo zbierana jest informacja  o liczbie  wystąpień  grafów z m wierzchołka-
mi  nienasyconymi.  Struktura  danych,  w  której  przechowuje  się  grafy,  może  być
wybrana dowolnie, ale tu przewidziano dalsze rozszerzenia przetwarzania listy, np.
o odsiewanie grafów, i z tego względu zastosowano strukturę, w której działa algo-
rytm  testowania  izomorfizmu  grafów.  Wykorzystano,  znane  z  poprzednich  roz-
działów, operacje tworzenia tablicy E, generacji grafu losowego G(n, J) oraz trans-
formacji E —> Gr reprezentacji grafu.

Algorytm konstruowania listy grafów losowych G(n,f)

Dane: n - liczba wierzchołków,/- maksymalny stopień, rep - rozmiar próbki.
Wynik: h - głowa listy grafów, Q

- licznik grafów z m wierzchołkami nienasy-

conymi (m = O, l, ...,f). Metoda:
1.  Przygotuj licznik Q.
2.  Przygotuj głowę listy grafów.
3.  Utwórz tablicę krawędzi E.
4.  Powtórz rep razy następujące operacje:

wygeneruj graf losowy G = G(n, f),

oblicz m - liczbę wierzchołków nienasyconych w G,

zwiększ Q

o1,

przepisz graf G z tablicy E do rekordu typu TGraph,

dopisz graf do początku listy.

Złożoność: O(n

Implementacja

const nmax = 13; kmax = nmax*(n max - 1) di v 2;
t y p e i n d = 1. n m a x ; i n dl = L. k m a x ;

r = record a,b:byte; code:Boolean end;
t = array[ind] of integer;

{ c }

t1 = array[indl] of r;

{ E }

tQ = array[0..nmax] of integer;

{ Q }

refl = ^eleml;
elem1 = record G:TGraph; next:refl; end;

procedure pushl(x:TGraph; var h:refl);
var p:ref1;
begin

new(p);

with p^ do begin G:=x; next:=h; end;
h:=p

end; { pushl }

procedure konstrflista(n,f,rep:integer; var h:ref1;

var Q:tQ);

var i,j,m,total:integer; E:tl; Gl:TGraph;
begin

for m:=0 to f do Q[m]:=0; { przygotowanie Q }
h:=nil;

{ przygotowanie listy }

init(n, E, total);

{ utworzenie tablicy E }

for i:=1 to rep do

begin

Gnf(n, f, total, E, c, k); { generacja Gnf }

m:=0;

for j:=1 to n do

if c[j] < f then m:=m + 1;

Q[m]:=Q[m] + 1;

{ aktualizacja Q }

transEGr(n, total, E, Gl);

{ A w G1 }

jeden(n, G1);

{ Deg i DegSort w G1 }

pushl(Gl, h);

{ Gl na pocz

ątek listy }

end; { i } end; {

konstrflista }

4.2. Tablica list

4.2.1. Konstruowanie tablicy list identyfikatorów

Tablica list i lista list są przykładami realizacji magazynu informacji o struktu-

rze skorowidza. Dostęp do informacji jest tu łatwiejszy niż w przypadku zwykłej
tablicy, pliku lub listy jednopoziomowej, ponieważ informacja jest sklasyfikowana
zgodnie z pewnym kryterium i umieszczona na oddzielnych listach.

Rozpatrzmy na początek tworzenie skorowidza w postaci tablicy list identyfi-

katorów. Niech identyfikatorem będzie ciąg liter i cyfr rozpoczynający się od litery
(zgodnie z gramatyką języka Pascal). Każda lista przechowuje identyfikatory roz-
poczynające się od tej samej litery.

W implementacji algorytmu zastosowano tablicę indeksowaną literami, która

przechowuje początki odpowiednich list. Założono, że identyfikatory znajdują się
w pliku input, każdy w oddzielnym wierszu.

Algorytm konstruowania tablicy list identyfikatorów

Dane: n - liczba identyfikatorów c-znakowych oraz ciąg identyfikatorów. Wynik:
B - tablica list identyfikatorów rozpoczynających się od tej samej litery. Metoda:
1.  Przygotuj tablicę B, w której przechowuje się początki list.
2.  Pobierz kolejny identyfikator x.
3.  Sprawdź, czy x znajduje się na liście identyfikatorów zaczynających się od tej

samej litery.

4. Jeśli nie, to dopisz x do tej listy (np. na początku listy).
Złożoność: O(n)

Rys. 4.2. Przykład skorowidza jako tablicy list identyfikatorów

const cmax =15; { max d

ługość identyfikatora }

type t = array[l..cmax] of char;

ref = ^elem;
elem = record a:t; next:ref end;

tB = array['a'..'z'] of ref;

{ B }

procedure czyt(c:integer; var x:t); { identyfikator }
var i: integer; begin

for i:=l to c do read(x[i]); readln;

end; { czyt }

function member(x:t; h:ref):Boolean;

{ ... }

end;{ member }

procedure push(x:t; var h:ref);

{ ... }

end; { push }

Implementacja

procedure konstrB (n:integer; var B:tB); var
ch:char; i:integer; p:ref; x:t; begin

for ch:='a' to 'z' do B[ch]:=nil;
for i:=1 to n do begin

czyt(c, x);
p:=B[x[l]] ;

if not member(x, p) then push(x, p); end; {

i } end; { konstrB }

4.2.2. Konstruowanie tablicy list grafów

W podobny sposób można skonstruować skorowidz zawierający grafy losowe,

np. G(n, p), podzielone na klasy według liczby krawędzi i przesiane ze względu na
izomorfizm. Tablica B jest indeksowana liczbami całkowitymi o wartościach od-
powiadających liczbie krawędzi grafów G(n,p), czyli od O do n(n - l)/2.

Algorytm konstruowania tablicy list grafów

Dane: n - liczba wierzchołków, p - prawdopodobieństwo krawędziowe, rep -
rozmiar próbki.
Wynik: B - tablica list grafów z k krawędziami, k = O, l,..., n(n - l)/2.
Metoda:

1. Przygotuj tablicę B.
2. Powtórz rep razy następujące operacje:

a. wygeneruj graf G = G(n, p) i oblicz k - liczbę krawędzi grafu,
b. przepisz graf G z tablicy A do rekordu typu TGraph,
c. jeżeli G nie jest elementem listy o głowie B[k], to dopisz G do tej listy.

Złożoność: Zależy od n i złożoności algorytmu testowania izomorfizmu grafów.

Implementacja

const nmax = 100; kmax = nmax*(nmax-1) div 2;
type ind = l..nmax;

indl=l..kmax;

t2 = array[ind,ind] of Boolean;

{ A }

t3 = array[ind] of byte;

{ Deg, DegSort }

TGraph = record A:t2; Deg,DegSort:t3 end;
ref = ^elem;
elem = record Gr:TGraph; next:ref; end;
tB = array[indl] of ref;

{ B }

procedure Gnp(n:integer;p:real;var A:t2;var krinteger);

{ -. . } end;
{ Gnp }

procedure transAGr(n:integer; var A:t2; var Gr:Tgraph);

{ ... }

end; {transAGr }

procedure jeden(n:integer; var Gr:TGraph);
{ ... } end; {jeden }

function memberGr(n:integer; x:TGraph; h:ref):Boolean;

var jest:Boolean;
begin

jest:=false;

while (h <> nil) and not jest do

if EqualGraphs(n, x, h

.Gr) {funkcja z modu

łu iso }

then jest:=true else h:=h^.next; member:=jest; end; {
memberGr }

procedure push(xrTGraph; var h:ref);
var p:ref;

begin

new(p); with p^ do begin Gr:=x; next:=h; end;
h: =p; end; {

push }

procedure konstrB(n,rep:integer; p:real; var B:tB);
var i,k:integer; A:t2; Gl:TGraph;
begin

for i:=0 to n*(n - 1) div 2 do B[i]:=nil;
for i:=l to rep do

begin

Gnp (n, p, A, k) ;
transAGr(n, A, Gl);
jeden(n, Gl);

if not member (n, Gl, B[k]) then push(Gl, B[k])

end; { i } end; { konstrB }

4.3. Lista wielopoziomowa

4.3.1. Konstruowanie listy list identyfikatorów

Skorowidz zrealizowany jako lista list zawiera wskaźniki początków tylko nie-

pustych list, zapamiętane na odrębnej liście. Rozważmy operację tworzenia takiego
skorowidza identyfikatorów.

Algorytm konstruowania listy list identyfikatorów

Dane: Plik n identyfikatorów c-znakowych.

Wynik: Lista list zawierających identyfikatory rozpoczynające się od tej samej
litery.

Metoda: Niech H oznacza początek listy pierwszych liter identyfikatorów.
1. Przygotuj H.
2. Przeglądając plik z danymi, wykonuj następujące operacje:

pobierz x - kolejny identyfikator,

sprawdź, gdzie na liście H znajduje się litera równa pierwszej literze w x,

jeśli tej litery nie ma na liście H, to dopisz ją do tej listy, utwórz, pierwszy
element odpowiadającej jej listy identyfikatorów i umieść w nim x;

w przeciwnym przypadku sprawdź, czy x znajduje się na wskazanej liście
identyfikatorów; jeśli go nie ma, to dopisz x do tej listy.

Złożoność: O(n), gdzie n jest długością pliku.

Implementacja

const cmax = 1 5 ; { max d

ługość identyfikatora }

type ind = l..cmax;

t = array[ind] of char;

{ identyfikator }

ref = ^elem;
elem = record a:t; next:ref; end; { lista ident. }
refp = ^r;
r = record

{ element listy pionowej }

a:char; next:ref; nextp:refp; end; procedure push(x:t; var
h:ref); { dla identyfikatora }

{ ... }

end; { push }

function member(x:t; h:ref):Boolean; { dla ident. }

{ .. . }

end; { member }

procedure pushp(x:char; var h:refp);
var p:re fp;
begin

new(p);
with p^ do

begin a:=x; next:=nil; nextp:=h; end;

h:=p end; {

pushp }

procedure memberp(x:char; h:refp; var gdzie:refp);
begin

gdzie:=nil;
while (h <> nil) and (gdzie = nil) do

if h^.a = x then gdzie:=h

else h:=h^.nextp;

end; { memberp }

procedure skorowidzl(n,c:integer; var H:refp);
var i:integer; x:t; gdzie:refp;
begin

H:=nil;
for i:=1 to n do

begin

czyt(c, x); { pobranie identyfikatora x }
memberp(x[1], H, gdzie); { gdzie jest x[l]? }
if gdzie = nil then begin

pushp(x[1], H);
push(x, H^.next);
end else

if not member(x, gdzie^.next) then

push(x, gdzie^.next) end;

end; { skorowidzl }

Przykład struktury skorowidza zrealizowanego jako lista list identyfikatorów

przedstawiono na rysunku 4.3.

Jeżeli chcemy utworzyć taki skorowidz dla informacji innego typu, np. dla gra-

fów podzielonych na klasy abstrakcji według wartości wybranego niezmiennika, to
musimy podać odpowiednie definicje struktur danych do reprezentacji elementów
listy poziomej (grafów) i listy pionowej (wartości niezmiennika).

Rys. 4.3. Przykład struktury skorowidza zrealizowanego jako lista list identyfikatorów

4.3.2. Generacja grafu losowego G(n, c)

Przedstawiamy jeszcze jeden algorytm generacji grafów losowych, w którym

dana  jest  liczba  wierzchołków  oraz  c  -  ciąg  stopni  wierzchołków,  a  grafy  są  loso-
wane  z  jednakowym  prawdopodobieństwem  ze  zbioru  wszystkich  takich  grafów
(oznaczonych). Jest to algorytm Rangraph  opublikowany przez N.C. Wormalda
w  1984  roku.  Algorytm  ten  jest  trudniejszy  w  realizacji  od  poprzednio  przedsta-
wionych algorytmów  generacji  grafów  losowych, a jego złożoność jest ponadkwa-
dratowa,  zwłaszcza  w  przypadku  generacji  grafów  regularnych  o  dużym  stopniu
wierzchołków.

Przed wykorzystaniem tego algorytmu należy sprawdzić, czy c jest ciągiem

graficznym, a więc czy istnieją grafy o takim ciągu stopni (por. [1]).

Główną strukturą danych, w której konstruuje się graf G = G(n, c), jest tablica L

o elementach typu całkowitego i długości równej podwojonej liczbie krawędzi
grafu. Przed rozpoczęciem właściwej generacji wprowadza się do tablicy L numery
/ wierzchołków grafu, l < / < n, każdy z nich c

razy. W implementacji algorytmu

wykorzystano dwie procedury: initL oraz Gnc. Gdy generuje się wiele grafów o
tym samym ciągu stopni, procedurę initL wykonuje się tylko raz, dla pierwszego

grafu.  Do  przechowywania  informacji  o  wygenerowanych  krawędziach  wykorzy-
stano  znaną  tablicę  kwadratową  A  (lokalną  w  procedurze  Gnć).  Rozwiązanie  to
można  ulepszyć,  używając  oszczędniejszej  struktury  danych.  Zmienna  last  prze-
chowuje informację o indeksie ostatniego elementu tablicy L.

Algorytm generacji grafu losowego G = G(n, c)

Dane: n - liczba wierzchołków grafu, c - ciąg stopni wierzchołków.
Wynik: L - tablica krawędzi losowego grafu G = G(n, c). Metoda:
1.  Przygotuj tablicę L zawierającą c[i] wystąpień wierzchołka /, i = l, 2, .... n.
2.  Podstaw zbiór pusty jako początkową wartość zbioru krawędzi grafu G.
3.  Losuj sąsiadów dla kolejnych wierzchołków z tablicy L (rozpoczynając od

ostatniego elementu tej tablicy) w następujący sposób:

jeżeli dla wierzchołka / zostanie wylosowany sąsiad o tym samym numerze
(pętla własna w grafie) lub ponownie zostanie wylosowana para wierz
chołków /, j (krawędź równoległa), to powtórz losowanie krawędzi od po
czątku, ale dla ostatnio uzyskanego stanu tablicy L;

w przeciwnym przypadku wylosowany element tablicy L zamień miejsca
mi z elementem poprzedzającym ten, dla którego wykonano losowanie,
i dodaj nową krawędź do grafu G (zaktualizuj zbiór krawędzi).

Złożoność: O(n

Implementacja

Rys. 4.4. Struktury danych do generacji grafu losowego G = G(n, c)

const nmax = 100; kmax = nmax*(nmax - 1) di v 2;
type ind = L.nmax;

indl = 1..kmax;
tL = array[indl] of integer;

{ L }

t2 = array[ind,ind] of Boolean;

{ A }

t=array[ind] of integer;

{ c }

procedure initL(n:integer; var c:t; var L:tL;

var last:integer); var

i,j,h:integer; begin h:=0; for i:=l to n do

for j:=l to c[i] do begin h:=h + 1; L[h]:=i; end;

last:=h end; { initL }

procedure Gnc(n, last:integer; var c:t; var L:tL);
var i,j,h,z:integer; A:t2; good:Boolean; begin

good:=false; while
not good do begin

good:=true;
for i:=1 to n do

for j:=l to n do A[i,j]:=false;

h:=last;
while (h >= 1) and good do

begin

i:=L[h];

{ wierzcho

łek }

z:=random(h - 1) + 1; { indeks s

ąsiada }

j:=L[z];

if i = j then good:=false { p

ętla własna }

else begin

if A[i,j] then good:=false { nie nowa }

else begin

A[i,j]:=true; A[j,i]:=true;
L[z]:=L[h-l]; L[h-l]:=j; h:=h - 2;
end;

end; { if } end; {

while h} end; { while
not } end; { Gnc }

4.3.3. Konstruowanie listy list grafów

Jeżeli struktura danych przechowująca wiele grafów powinna uwzględniać po-

dział grafów na klasy według wartości niezmiennika z szerokiego zakresu, ale
przyjmującego tylko niektóre wartości, to warto wykorzystać listę do przechowy-

wania wartości niezmiennika i grupować reprezentacje grafów na odpowiednich
listach, tak jak w poprzednim algorytmie zaprojektowanym dla identyfikatorów.

Wybierzmy liczbę trójkątów jako niezmiennik losowych grafów regularnych

generowanych za pomocą algorytmu G(n, c).

Algorytm konstruowania listy list grafów

Dane: n - liczba wierzchołków, r - stopień wierzchołka, rep - rozmiar próbki.
Wyniki: H - lista list nieizomorficznych grafów regularnych z podziałem na listy
według liczby trójkątów w tych grafach. Metoda:
1. Przygotuj H.
2. Powtórz rep razy następujące operacje:

a. wygeneruj graf losowy G = G(«, c) i oblicz c

- liczbę trójkątów w G,

b. sprawdź, gdzie na liście wartości niezmiennika znajduje się wartość c

c. jeśli nie ma jej na tej liście, to ją dopisz oraz dopisz G do wskazanej listy

grafów (G będzie pierwszym elementem tej listy),

d. jeśli

, znajduje się na liście H, to sprawdź, czy graf G jest izomorficzny z

jakimś elementem listy i jeśli odpowiedź jest „nie", to dopisz G do tej listy.

Złożoność: zależy od liczby wierzchołków «, stopnia wierzchołków r oraz od zło-

żoności algorytmu testowania izomorfizmu grafów.

4.4. Tablica mieszająca

4.4.1. Konstruowanie tablicy mieszającej identyfikatorów

Tablice mieszające wykorzystuje się w sytuacjach, gdy szybkie wyszukiwanie

zgromadzonej informacji jest ważną cechą projektowanego algorytmu. Informacje
są wprowadzane do elementu  tablicy  o  indeksie  obliczonym  jako  wartość  funkcji
mieszającej.  Argumentem  tej  funkcji  jest  wprowadzana  informacja,  np.  identyfi-
kator lub graf. Jeśli element tablicy o tym indeksie jest wolny, to informacja może
być tam umieszczona; jeśli jest zajęty przez inną informację, należy obliczyć war-
tość  indeksu  wtórnego,  najlepiej  stosując  dodawanie  kwadratu  przyrostu.  Dalsze
szczegóły dotyczące tablic mieszających można znaleźć w książce [7, rozdz. 4.6].

W implementacji algorytmu konstruowania tablicy mieszającej identyfikatorów

przewidziano  ograniczoną  długość  identyfikatora.  Długie  identyfikatory  można
podzielić  na  części  i  przechowywać  na  liście  wskazywanej  przez  pierwszą  część,
znajdującą się w tablicy. Pole a rekordu będącego elementem tablicy jest wykorzy-
stywane do przechowywania informacji o tym, czy element jest wolny czy zajęty.
W przypadku  identyfikatorów  jest  to często  liczba  całkowita  oznaczająca  kolejny
numer identyfikatora.

Algorytm konstruowania tablicy mieszającej identyfikatorów

Dane: n - długość ciągu identyfikatorów, ciąg identyfikatorów c-znakowych.
Wynik: H - słownik identyfikatorów w tablicy mieszającej. Metoda: Założenia:
długość tablicy musi być liczbą pierwszą, tablica zawiera dodatkową informację
o tym, czy element tablicy jest wolny; w przypadku kolizji poszukuje się
indeksu wtórnego metodą kwadratową.
1. Przygotuj tablicę H (wszystkie elementy są oznaczone jako wolne, np. przez

wstawienie liczby równej hmax).

2. Powtórz n razy następujące operacje:

a. pobierz identyfikator x z ciągu wejściowego, oblicz indeks pierwotny;
b. jeżeli to miejsce jest wolne, wstaw x oraz oznacz miejsce jako zajęte (np.

kolejny numer wstawianego identyfikatora);

c. jeżeli miejsce jest zajęte przez inną informację, to szukaj indeksu wtórnego

i wstaw x w to miejsce tablicy.

Złożoność: O(cn).

Implementacja

Rys. 4.5. Przykład struktury tablicy mieszającej

const cmax = 15; hmax = 501; nmax = 400; {max. wypeln.}
type ind = 0..hmax - 1;

t = array[1..cmax] of char; rH =
record a:integer; b:t; end; tH =
array[ind] of rH;

function hash(c:integer; var x:t):integer;
var h,i:integer; begin h:=l;
for i:=l to c do h:=(h * ord(x[i])) mod hmax;
hash:=h end; { hash } procedure insert(x:t;
j:integer; var nr:integer;

var H:tH);

begin

with H[j] do begin a:=nr; b:=x; end;
nr:=nr + 1; end; { insert }
procedure konstr(n,c:integer; var H:tH );
var i:integer; free:Boolean; begin

nr:=l; for i:=0 to hmax - 1 do H[i].a:=hmax;
for i:=l to n do begin

czyt(c, x); {pobranie identyfikatora }
j:=hash(c, x);{ obliczenie indeksu pierwotnego }
if H[j].a = hmax then insert(x, j, nr, H) else

if H[j].b <> x then { indeks wtórny }

begin

m:=0; free:=false;
while not free do
begin

m:=m + 1; j:=(j + sqr(m)) mod hmax;
if H[j].a = hmax then begin

free:=true; insert(x, j,
nr, H) end

else if H[j].b = x then free:=true

end;

end; { else } end;

{ i } end; { konstr }

4.4.2. Wyszukiwanie informacji w tablicy mieszającej

Podany niżej algorytm służy do udzielenia odpowiedzi na pytanie, gdzie znaj-

duje się informacja w tablicy mieszającej. W implementacji tego algorytmu wyni-
kiem jest indeks równy zeru, jeśli nie znaleziono danej informacji.

Algorytm wyszukiwania informacji w tablicy mieszającej

Dane: x - identyfikator c-znakowy, r - liczba powtórzeń, H - tablica mieszająca.

Wynik: Informacja o tym, gdzie x znajduje się w tablicy H.

Metoda:

1. Oblicz indeks pierwotny.
2. Sprawdź, czy x znajduje się w tym miejscu tablicy H. Jeśli nie, to obliczaj in

deks wtórny (ale nie więcej niż r razy) i sprawdzaj, czy x znajduje się w tym
miejscu.

3. Jeśli nie, to wynikiem jest indeks o wartości O, co oznacza, że nie znaleziono x

w tablicy H.

Złożoność: O(r).

Implementacja

function search(r,c:integer; x:t; var H:tH):integer;

var j,m:integer; jest:Boolean;

begin

j:=hash(c, x) ;
jest:=false;
m:=0;

while (m <= r) and not jest do

if H[j].b = x then jest:=true
else begin

m:=m + l;

j:=(j + sqr(m)) mod hmax;

end;

if jest then search:=j else search:=0;

end; {search }

5. STRUKTURY DRZEWIASTE

5.1. Drzewa binarne

5.1.1. Konstruowanie losowego drzewa binarnego

Przegląd struktur drzewiastych rozpoczynamy od przedstawienia podstawo-

wych operacji na  drzewach  binarnych,  czyli takich,  w których  każdy  wierzchołek
ma  co  najwyżej  dwa  następniki',  lewy  i  prawy.  Jeden  z  wierzchołków  jest  wyróż-
niony,  nazywamy  go  korzeniem.  Wierzchołki  nie  mające  następników  nazywamy
wierzchołkami  wiszącymi  lub  liśćmi.  Pozostałe  wierzchołki  nazywamy  wewnętrz-
nymi. Wszystkie wierzchołki znajdujące się na lewo od  korzenia  należą  do lewego
poddrzewa, a wierzchołki znajdujące się na prawo od korzenia - do prawego pod-
drzewa.  Poza  tym  dla  każdego  wierzchołka  wyróżnia  się  jego  lewe  i  prawe  pod-
drzewo.

Mówimy, że wierzchołek znajduje się na poziomie k drzewa binarnego, jeśli je-

go odległość od korzenia jest równa k. Przyjmuje się, że poziom korzenia jest rów-
ny 1. Wysokością drzewa jest odległość najdalszego liścia od korzenia. Drzewo
przedstawione na rysunku 5. l ma wysokość równą 3.

lewe poddrzewo

prawe poddrzewo

Rys. 5.1. Struktura drzewa binarnego

Przedstawimy kilka rodzajów drzew binarnych: losowe drzewo binarne, drzewo

binarne poszukiwań, drzewo dokładnie wyważone, drzewo Wirtha oraz kopiec.

Podobnie jak w przypadku tablic, plików i list, przedstawiamy najpierw metodę

konstruowania losowego drzewa binarnego RBT (ang. Random Binary Tree)

0 danej liczbie wierzchołków. Losowany jest nie tylko ciąg liczb całkowitych
wprowadzanych do drzewa (z zakresu od l do z), ale również podczas przeglądania
już zbudowanego drzewa w celu znalezienia lokalizacji nowego elementu (liścia)
losuje się kierunek dalszego przeglądania i z prawdopodobieństwem/) wybiera się
lewe poddrzewo (czyli prawe poddrzewo z prawdopodobieństwem l -p).

W implementacji każdego drzewa binarnego wykorzystuje się rekordy o co

najmniej trzech polach: jednym - informacyjnym (pole a np. typu całkowitego)
1dwóch wskazujących na lewe i prawe poddrzewo (pola left i right typu wskaźni
kowego).

Drzewo BRT przedstawione na rysunku 5.2 wygenerowano dla następujących

danych: n = 6, z = 100, p = 0.5. O wygenerowanym ciągu liczb losowych można
powiedzieć, że pierwszym elementem była liczba 10, która znajduje się w korzeniu
drzewa, oraz że co najmniej jedna z liczb znajdujących się w liściach drzewa była
ostatnim elementem ciągu.

Strukturę losowego drzewa binarnego wykorzystuje się przede wszystkim do

testowania algorytmów działających na drzewach binarnych, np. do przeglądania,
obliczania wysokości, testowania izomorfizmu dwóch drzew.

Rys. 5.2. Przykład struktury losowego drzewa binarnego RBT

Algorytm konstruowania losowego drzewa binarnego

Dane: n - długość ciągu liczb, p - prawdopodobieństwo lewostronne, z - zakres

losowania.

Wynik: t - korzeń losowego drzewa.

Metoda:

1. Przygotuj drzewo.
2. Powtórz n razy losowanie liczby całkowitej x z przedziału [l, z] i wstawianie x

do drzewa za pomocą rekurencyjnej operacji insert w następujący sposób:
a. jeśli drzewo (poddrzewo) jest puste, to wygeneruj nowy element i umieść

w nim x oraz informację o pustym lewym i prawym następniku;

b. w przeciwnym przypadku losuj liczbę z przedziału (O, 1) i jeżeli jest ona

mniejsza lub równa wartości prawdopodobieństwa/?, to szukaj miejsca dla
x w lewym poddrzewie, a jeśli jest większa od p, to w prawym poddrzewie.

Złożoność: O(n).

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

procedure insertRBT(x:integer; p:real; var t:ref);
begin

if t = nil then

begin

new(t) ;
with t^ do begin a:=x; left:=nil; right:=nil end

end

else

if random <= p then insertRBT (x, p, t^. left)

else insertRBT(x, p, t^.right);

end; { insertRBT }

procedure konstrRBT(n, z:integer; p:real; var trref);
var i, x:integer; begin t: =nil ;

for i:=1 to n do

begin

x:=random(z) + 1;
insertRBT(x, p, t) end;
end; { konstrRBT }

5.1.2. Przeglądanie drzewa binarnego

Systematyczne przeglądanie drzewa binarnego można wykonać w jednym

z  trzech  naturalnych  porządków  odwiedzania  wierzchołków  i  ich  następników
(oraz  w  trzech  dodatkowych,  w  których  zamieniono  kolejność  „lewy,  prawy"  na
odwrotną).  Są  to  następujące  porządki:  preorder,  inorder  i  postorder,  różnią  się
one  kolejnością odwiedzania wierzchołka w stosunku do  jego  następników.  Wyko-
rzystuje  się  je  np.  w  algorytmach  wyprowadzania  struktury  zbudowanego  drzewa
binarnego.  Dalsze  informacje  o  przeglądaniu  drzew  można  znaleźć  w  książce
[7,  rozdz.  4.4.2].  Rysunek  5.3  przedstawia  kolejność  przeglądania  drzewa  o  8
wierzchołkach z zastosowaniem wymienionych trzech porządków.

preorder

inorder

postorder

Rys. 5.3. Przykład przeglądania drzewa binarnego w trzech porządkach (liczby wskazują kolejność

odwiedzania wierzchołków)

Algorytm przeglądania drzewa binarnego

Dane: t - korzeń dowolnego drzewa binarnego.

Wynik: Ciąg informacji z kolejnych wierzchołków drzewa w odpowiednim po-
rządku. Metoda:
1. preorder. odwiedź korzeń t, odwiedź jego lewe poddrzewo w ten sam sposób,

odwiedź jego prawe poddrzewo w ten sam sposób,

2. inorder: odwiedź lewe poddrzewo wierzchołka t, następnie wierzchołek / oraz

prawe poddrzewo wierzchołka t,

3. postorder: odwiedź lewe poddrzewo wierzchołka t, potem jego prawe pod

drzewo oraz wierzchołek t.

Złożoność: O(n), gdzie n jest liczbą elementów drzewa.

70 Implementacja

t y p e r ef =

ele m;

e l e m = r e c o r d a : i n t e g e r ; l e f t, r i g h t : re f e n d ;

p r o c e d u r e p r e o r d e r ( t : r e f ) ; b e g i n

if t < > nil t h e n

b e g i n
w r i t e ( o u t , t

. a, ' ' ) ;

p r e o r d e r ( t

. l e f t ) ; p r e o r d e r

( t

. r i g h t ) ; e n d ;

e n d ; { pr e or d er } p r o c e d u r e
i n o r d e r ( t : r e f ) ; b e g i n

i f t O n i l t h e n

b e g i n
i n o r d e r ( t

. l e f t ) ; w r i t e

( o u t, t

. a , ' ' ) ; i n o r d e r ( t

. r i g h t ) ; e n d ;

e n d; { i n or d er } p r o c e d u r e
p o s t o r d e r ( t : r e f ) ; b e g i n

if t < > nil t h e n

b e g i n

p o s t o r d e r ( t

. l e f t ) ; p o s t o r d e r ( t

. ri g h t ) ; w r it e ( o u t , t

. a , ' ' ) ;

e n d ; e n d ; { p o st or d e r }

5.1.3. Wyprowadzanie informacji z drzewa binarnego

Przedstawiamy kilka algorytmów wyprowadzania struktury zbudowanego

drzewa wraz z zapisaną w nim informacją. Pierwszy z tych algorytmów przegląda
drzewo według  preorder, ujmuje  poddrzewa w  nawiasy  kwadratowe,  a  lewe  pod-
drzewo oddziela od prawego znakiem „ ; ". Drugi algorytm przegląda drzewo we-
dług  inorder,  ujmuje  poddrzewa  w  nawiasy  okrągłe,  a  puste  poddrzewa  oznacza
symbolem gwiazdki „*". Algorytmy te są łatwe do zaprojektowania, ale odczytanie
struktury  zbudowanego  drzewa  jest  kłopotliwe  nawet  w  przypadku  drzew  o  10
wierzchołkach.

Trzeci algorytm, zaproponowany przez Wirtha (por. [7], str. 209), ale ze zmie-

nioną  kolejnością  odwiedzania na „prawy  - lewy",  wyprowadza drzewo  nie
w postaci ciągu znaków, ale z wykorzystaniem drugiego wymiaru na płaszczyźnie
-  rozmieszcza  informację  pobraną  z  wierzchołków  tak,  aby  po  dorysowaniu  kra-
wędzi powstał  odwrócony  o 90° rysunek  drzewa  binarnego.  Przykłady  wykonania
tych trzech algorytmów przedstawiono na rysunku 5.4.

Rys. 5.4. Przykłady wyprowadzania informacji z drzewa binarnego

Algorytm wyprowadzania informacji z drzewa binarnego

Dane: t - korzeń dowolnego drzewa binarnego.

Wynik: Informacja przechowywana w wierzchołkach drzewa oraz struktura drze-
wa, zgodnie z wybranym algorytmem wyprowadzania: tekstowo (druki, druki) lub
w postaci półgraficznej (druk3). Metoda:
1. druki: odwiedzanie wierzchołków wpreorder, lewe i prawe poddrzewa ujęte

w nawiasy [, ] i oddzielone znakiem „ ; ".

2. druki', odwiedzanie wierzchołków w inorder, lewe i prawe poddrzewa ujęte

w nawiasy (,), a puste poddrzewa oznaczone jako „*".

3. druki: odwiedzanie wierzchołków w odwrotnym inorder (najpierw prawe

poddrzewo) i drukowanie informacji z odstępami. Jeśli obrócimy wyprowa-
dzoną strukturę o 90° i uzupełnimy krawędziami, to otrzymamy czytelną po-
stać struktury drzewa.

Złożoność: O{n).

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

procedure druki(t:ref);

{ w preorder }

begin

if t <> nil then

with t^ do begin

write(out,' ',a,' '); write(out,'[');
drukl(left); write(out,';');
drukl(right); write(out,']') end;

end; { drukl }

procedure druk2(t:ref);

{ w inorder }

begin

if t <> nil then

with t^ do begin

write(out,'(');

druk2(left); write(out,' ',a,' ')/
druk2(right); write(out,')'); end

else write(out, '*');

end; { druk2 }

procedure druk3(t:ref; h:integer); { wg N. Wirtha }
var i:integer;

{ h - wci

ęcie }

begin

if t o nil then

with t^ do begin

druk3(right, h + 3); for i:=1 to h do
write(out,

'); writeln(out,a);

druk3(left, h + 3); end; end; { druk3
}

5.1.4. Poszukiwanie informacji w drzewie

Operacja poszukiwania informacji w dowolnym drzewie binarnym wymaga

w najgorszym przypadku odwiedzenia wszystkich wierzchołków drzewa.

Algorytm poszukiwania informacji w drzewie

Dane: x - poszukiwana informacja (np. liczba całkowita), t - korzeń drzewa.
Wynik: Informacja o tym, czy x znajduje się w drzewie.
Metoda:
1. Jeśli drzewo nie jest puste, to porównaj x z informacją w korzeniu drzewa. Jeśli

są równe, to znaleziono x.

2. "W przeciwnym przypadku przeszukaj lewe poddrzewo i jeśli nie znajdziesz

w nim x, to przeszukaj prawe poddrzewo.

Złożoność: O(n).

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

procedure member(x:integer; trref; var jest:Boolean);
begin

if t O nil then

with t~ do

if x = a then jest:=true

else begin

member(x, left, jest);

if not jest then member(x, right, jest)

end

else jest:=false

end; { member }

5.1.5. Obliczanie wysokości drzewa

Wysokość drzewa binarnego jako struktury danych powinna być jak najmniej-

sza. Najgorszy przypadek zachodzi, gdy w każdym elemencie drzewa brak jednego
następnika (drzewo jest listą) - wtedy jego wysokość jest równa liczbie elemen-
tów.

Przedstawiamy dwie realizacje algorytmu obliczania wysokości drzewa, które

wyznaczają liczbę poziomów, i w związku z tym, aby otrzymać informację o wy-
sokości, należy od liczby poziomów odjąć l. W pierwszej realizacji wykorzystano
pomocniczą operację wyznaczania większej z dwóch liczb, tak aby operację obli-

czenia wysokości można było zaprojektować wprost z definicji wysokości drzewa.
Druga realizacja jest funkcją rekurencyjną.

Algorytm obliczania wysokości drzewa binarnego

Dane: t - korzeń dowolnego drzewa binarnego.

Wynik: Wysokość drzewa.

Metoda (rekurencyjną): Jeżeli drzewo jest puste, to jego wysokość jest równa zeru.

W przeciwnym przypadku oblicz wysokość lewego i prawego poddrzewa, wybierz

większą z nich i powiększ o l.
Złożoność: O(n), gdzie n jest liczbą elementów drzewa.

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end; {

funkcje height i heightl wyznaczaj

ą liczbę poziomów:}

function wi

ększy(a,b:integer):integer;

{ Tomasz Obrebski, Inf., 1989 }

begin

if a > b then wi

ększy:=a else większy:=b

end; { wi

ększy } function

height(t:ref):integer; begin

if t <> nil then

height:=wiekszy(height(t^.left), height(t^.right)) + 1
else height:=0 end; { height }

function heightl(t:ref):integer;

{ Andrzej Urbanski, 1988}

var x,y:integer; begin

if t <> nil then

with t

do begin

x:=heightl(left);
y:=heightl(right);
if x > y then heightl:=x + 1

else heightl:=y + 1;

end

else height1:=0;

end; { heightl }

5.1.6. Poszukiwanie największego elementu w drzewie

Jeżeli należy znaleźć największy (lub najmniejszy) element w drzewie binar-

nym, to postępowanie jest podobne do przyjętego w odniesieniu do tablic. Za każ-
dym razem należy przejrzeć całą strukturę, ale za najgorszy przypadek należy
uznać ten, w którym każdy odwiedzany wierzchołek zawiera informację lepszą,
tzn. liczbę o większej wartości, od dotychczas znalezionej.

Algorytm poszukiwania największego elementu w drzewie binarnym

Dane: t - korzeń drzewa binarnego przechowującego liczby całkowite.
Wynik: Wartość największego elementu w drzewie.
Metoda: Jeżeli drzewo nie jest puste, to zakładamy początkowo, że m - najwięk-
szy element - znajduje się w korzeniu drzewa. Następnie przeszukujemy drzewo
w preorder, aktualizując każdorazowo wartość m, jeśli w odwiedzanym wierzchoł-
ku znajdziemy wartość większą niż m. Złożoność: O(n), gdzie «jest liczbą
elementów drzewa.

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

procedure szukaj(t:ref; var m:integer); { w preorder }
begin

if t <> nil then

begin

if (t^.a > m) then m:=t^.a;
szukaj(t^.left, m);
szukaj(t^.right, m); end

end; { szukaj } function
max(t:ref):integer; var
naj:integer; begin

if t O nil then

begin

naj:=t^.a;
szukaj(t, naj)
end;

max:=naj;

end; { max }

5.1.7. Testowanie izomorfizmu drzew binarnych

Dwa drzewa binarne uważamy za izomorficzne, jeżeli po ewentualnej zamianie

lewych lub prawych następników mają tę samą strukturę. Na rysunku 5.5 przed-
stawiono ilustrację tej relacji (oznaczonej symbolem = ).

Rys. 5.5. Dwa przykłady izomorficznych drzew binarnych

Algorytm testowania izomorfizmu drzew binarnych

Dane: tl, (2 - korzenie dwóch drzew binarnych.

Wynik: Informacja o tym, czy drzewa tl i t2 są izomorficzne.
Metoda (rekurencyjna): Jeżeli tl i t2 są puste, to odpowiedź jest „tak". Jeśli jedno
z nich jest puste, to odpowiedź jest „nie". Jeżeli żadne z drzew nie jest puste i lewe
poddrzewa są izomorficzne, to porównaj prawe poddrzewa; jeśli lewe poddrzewa
nie są izomorficzne, to porównaj prawe poddrzewo tl z lewym poddrzewem tl
i jeśli są izomorficzne, to sprawdź, czy lewe poddrzewo tl i prawe poddrzewo t2
są izomorficzne.

Złożoność: O(n), gdzie n jest liczbą elementów drzewa.

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

function izo(tl, t2:ref):Boolean;

begin

{ Robert Jamro

ży, Inf., 1990 }

if (tl = nil) or (t2 = nil) then

izo:=tl = t2 else if
izo(t1^.left, t2^.left)

then izo:=izo(tl^.right, t2^. right)
else if izo(tl^.right, t2^.1eft)

then izo:=izo (tl^.left, t2^. right) else izo:=false;
end; { izo }

5.2. Binarne drzewo poszukiwań

5.2.1. Konstruowanie losowego drzewa BST

Binarne drzewo poszukiwań BST (ang. Binary Search Tree) jest ważną struktu-

rą danych ze  względu  na  wewnętrzne uporządkowanie informacji. Jeżeli  rozważa-
my drzewo BST przechowujące liczby całkowite, to w lewym poddrzewie  każdego
wierzchołka znajdują się liczby mniejsze od znajdującej się w danym wierzchołku,
a  w  jego  prawym  poddrzewie  -  większe.  W  tak  określonym  drzewie  BST  każdy
wierzchołek  przechowuje  inną  liczbę  i  jeżeli  w  ciągu  wejściowym,  z  którego  two-
rzymy  drzewo  BST,  występują  powtórzenia  informacji,  to  tylko  pierwsze  wystą-
pienie będzie wprowadzone do tego drzewa. Należy o tym pamiętać, jeżeli chcemy
zbudować losowe drzewo o dokładnie n wierzchołkach.

Wymienimy tu dwie istotne zalety tej struktury danych. Pierwsza z nich to fakt,

że operacje poszukiwania w BST wymagają przejrzenia tylko jednej ścieżki. Druga
wynika z łatwości sortowania - aby otrzymać ciąg posortowany, wystarczy odwie-
dzić wierzchołki w odpowiednim porządku (jeśli ciąg ma być posortowany rosną-
co, to wierzchołki są odwiedzane według inorder).

W implementacji algorytmu przedstawiono przykład drzewa BST wygenerowa-

nego  dla  następujących  danych:  n  =  7, z  =  100  (por. rysunek  5.6).  Podobnie  jak
przy  generacji  drzewa  RBT,  o  ciągu  wylosowanych  liczb  możemy  powiedzieć
tylko  tyle,  że  jego  pierwszym  elementem  była  liczba  27,  a  ostatnim  jedna  z  liczb
umieszczonych w liściu drzewa.

Algorytm konstruowania losowego drzewa BST

Dane: n - długość ciągu liczb, z - zakres losowania.
Wynik: t - korzeń drzewa BST.
Metoda:
1. Przygotuj drzewo.
2. Powtórz n razy losowanie liczby x z przedziału [l, z] i wstawianie x do drzewa

BST za pomocą operacji insert w następujący sposób:

jeśli t wskazuje na puste poddrzewo, to wygeneruj nowy element wskazy
wany przez t i umieść w nim informację x oraz informację o pustym lewym
i prawym następniku,

b. w przeciwnym przypadku szukaj w drzewie BST miejsca, w którym można

dopisać x, czyli jeśli wartość x jest mniejsza od wartości znalezionej w ko
lejnym wierzchołku drzewa, to szukaj w lewym poddrzewie, a jeśli nie -
szukaj w prawym poddrzewie.

Złożoność: O(ri).

Rys. 5.6. Przykład struktury drzewa BST

type ref = ^elem;

elem = record a:integer; left, right:ref; end;

procedure insert(x:integer; var trref); begin

if t = nil then

begin new(t) ;

with t^ do begin a:=x; left:=nil; right:=nil end;

end else if x <> t^.a then

if x < t ^.a then insert(x, t^.left)

else insert(x, t^.right);

end; { insert }

procedure konstrl(n, z:integer; var t:ref);
var i,x:integer; begin t:=nil;

for i:=l to n do

begin

x:=random(z) + 1;
insert(x, t); end; end; {
konstrl }

Implementacja

5.2.2. Poszukiwanie informacji w drzewie BST

Przedstawiamy dwie realizacje algorytmu poszukiwania informacji w drzewie

BST  -  iteracyjną  i  rekurencyjną.  Poszukiwania  ograniczają  się  do  odwiedzenia
tylko jednej ścieżki  drzewa od  korzenia do znalezionego  wierzchołka lub do końca
ścieżki (gdy nie  ma w  drzewie poszukiwanej  informacji). Najgorszy przypadek to
drzewo o jednej ścieżce o długości n, w którym nie ma poszukiwanej informacji.

Algorytm poszukiwania informacji w drzewie BST

Dane: x - informacja (np. liczba całkowita), t - korzeń drzewa BST. Wynik:
Informacja o tym, czy x jest elementem drzewa o korzeniu t. Metoda: Przeglądaj
kolejne wierzchołki, rozpoczynając od korzenia drzewa. Jeżeli wartość x jest
mniejsza od informacji znalezionej w wierzchołku, to dalsze poszukiwania
prowadź w lewym poddrzewie, w przeciwnym przypadku - w prawym
poddrzewie. Zakończ poszukiwanie, jeśli znajdziesz x lub jeśli wierzchołek jest
liściem. Złożoność: O(n).

Implementacja

type ref =

elem;

elem = record a:integer; left, right:ref end;

procedure member(x:integer; trref; var jest:Boolean);

{ iteracyjn

ą }

begin

jest:=false;

while (t O nil) and not jest do if

x = t^.a then jest:=true else

if x < t^.a then t:=t

.left

else t:=t

.right;

end; { member }

procedure memberl(x:integer; trref; var jest:Boolean);

{ rekurencyjn

ą }

begin

jest:=false;
if t O nil then

if x = t^.a then jest:=true

else

if x < t~.a then memberl(x, t^.left, jest)

else memberl(x, t^.right, jest);

end; { memberl }

5.2.3. Wyszukiwanie największego elementu w drzewie BST

Największy element w drzewie BST znajduje się w prawym poddrzewie na

skrajnej prawej ścieżce. Przedstawiamy dwie realizacje: iteracyjną i rekurencyjną.

Algorytm wyszukiwania największego elementu w drzewie BST

Dane: t - korzeń drzewa BST. Wynik: m -
największy element w drzewie.
Metoda: Przechodzimy od korzenia po skrajnej prawej ścieżce i na jej końcu znaj-
dujemy element o największej wartości. Złożoność: O(n), gdzie n jest liczbą
elementów drzewa. Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref end;

procedure max(t:ref; var m:integer); { iteracyjn

ą }

begin

if t O n i l th en

while f. right <> nil do t:=t^.right;

m:=t^. a; end; { max }

procedure maxl(t:ref; var m:integer); { rekurencyjn

ą }

begin

if f*. right = nil then m:=t^.a

else max1(t^.right, m)

end; { maxl }

5.2.4. Usuwanie informacji z drzewa BST

Jeżeli chcemy usunąć zbędną informację z drzewa BST, to operację tę należy

zaprojektować tak, aby  nie  zniszczyć  wewnętrznego  uporządkowania  elementów
w tym drzewie. Jeśli usuwamy informację, która znajduje się w liściu drzewa lub
w  wierzchołku,  który  ma  tylko  jeden  następnik,  to  operacja  polega  na  usunięciu
liścia  lub  ominięciu  wierzchołka.  Gdy  usuwany  wierzchołek  ma  dwa  następniki,
wybieramy  jedno  z  dwóch  rozwiązań.  W  pierwszym  najpierw  wyszukujemy
w drzewie informację, którą można umieścić zamiast usuwanej. Będzie to informa-
cja znajdująca się w jednym z liści: w lewym poddrzewie na skrajnej prawej ścieżce
lub  w prawym  poddrzewie  na  skrajnej  lewej  ścieżce  (nie  jest  istotne,  którą  z
nich wybierzemy). Po przeniesieniu tej informacji na miejsce, gdzie znajdowała się
informacja do usunięcia, usuwamy zbędny już liść.

Drugie rozwiązanie polega na przyłączeniu prawego poddrzewa usuwanego

wierzchołka do największego elementu w jego lewym poddrzewie, a następnie
usunięciu tego wierzchołka (ma on już teraz tylko lewe poddrzewo).

Należy pamiętać o zwolnieniu pamięci zajmowanej dotychczas przez usuwany

wierzchołek.

Na rysunku 5.7 pokazano usuwanie wierzchołka z drzewa BST z wykorzysta-

niem pierwszej z opisanych metod (usuwa się wierzchołek zawierający liczbę 5 -
informację tę zastępujemy informacją ze skrajnej prawej ścieżki w lewym pod-
drzewie, czyli liczbą 3, wierzchołek, który zawierał liczbę 3, usuwamy z drzewa).

Rys. 5.7. Przykład usuwania informacji z drzewa BST pierwszą metodą

Pierwszy algorytm usuwania informacji z drzewa BST

Dane: x - informacja (np. liczba całkowita), t - korzeń drzewa BST.
Wynik: t - korzeń drzewa BST po usunięciu x.
Metoda:

1. Jeżeli w drzewie znajduje się wierzchołek zawierający x, to sprawdź liczbę

jego poddrzew:

jeżeli ma co najwyżej jedno poddrzewo, to usuń (jeśli jest liściem) lub
omiń (jeśli ma jedno poddrzewo) ten wierzchołek;

b. jeżeli ma dwa poddrzewa, to wyszukaj największy element w jego lewym

poddrzewie (łub najmniejszy w prawym poddrzewie), wstaw tę informację
zamiast x i usuń znaleziony wierzchołek.

Zwolnij pamięć, którą zajmował usunięty wierzchołek.

Złożoność: O(n), gdzie n jest liczbą elementów drzewa

Implementacja

type ref = ^elem;

elem = record a: integer; left, right: ref end;

procedure delete (x : integer; var t:ref);

{ wg N. Wirtha [7], str.224 }

var p:ref;

procedure zamiana (var r:ref);
begin

if r^. right <> nil then zamiana (r" .right )

else begin

p^ . a:=r^ . a;
p:=r;

end; end; {

zamiana }

begin { delete }

if t <> nil then

if x < t^.a then delete (x, t'.left)

else

if x > t^.a then delete (x, t" . right)

else { x = t^.a } begin { usuwanie }

p:=t;

{ pomocniczy wska

źnik }

if p^.left = nil then t:=t^.right

else

if p^. right = nil then t:=t^.left

else zamiana (p^ . left ) ; dispose (p) ;

end; { usuwanie } end; { delete }

Drugi algorytm usuwania informacji z drzewa BST

Dane: x - informacja (np. liczba całkowita), t - korzeń drzewa BST.
Wynik: t - korzeń drzewa BST po usunięciu x.
Metoda:

1. Jeżeli w drzewie znajduje się wierzchołek zawierający x, to sprawdź liczbę

jego poddrzew:

a. jeżeli ma co najwyżej jedno poddrzewo, to usuń (jeśli jest liściem) lub

omiń (jeśli ma jedno poddrzewo) ten wierzchołek;

b. jeżeli ma dwa poddrzewa, to wyszukaj największy element w jego lewym

poddrzewie i dołącz do niego prawe poddrzewo x; omiń wierzchołek x,
który ma teraz tylko jedno (lewe) poddrzewo.

2. Zwolnij pamięć, którą zajmował usunięty wierzchołek.

Złożoność: O(ri), gdzie n jest liczbą elementów drzewa.

Implementacja

type ref = ^elem;

elem = record a:integer; left, right:ref; end;

procedure szukajprawego(p:ref; var r:ref);
begin

if p^.right <> nil

then szukajprawego(p^.right, r)
else r:=p; end; {

szukajprawego }

procedure deleteM(x:integer; var t:ref);

{ Leszek Masadynski, 1988 }

var p:ref; begin

if t o nil then if

t^.a = x then

if t^.left = nil then t:=t

.right

else begin

szukajprawego(t

.left, p);

p^.right:=t~.right; p:=t;

t:=t^.left;
dispose(p) end else

if t^.a > x then deleteM(x, t^.left)

else deleteM(x, t^.right)

end; { deleteM } ______________________________________

Na rysunku 5.8 pokazano usuwanie wierzchołka z drzewa BST z wykorzysta-

niem drugiej metody.

Rys. 5.8. Przykład usuwania wierzchołka z drzewa BST drugą metodą

5.2.5. Reorganizacja drzewa BST

Jeżeli informacja przechowywana w drzewie BST ma dodatkowy atrybut i wy-

magamy, aby dostęp do informacji był tym łatwiejszy, im większa jest wartość
atrybutu, to należy zreorganizować dane drzewo BST. Rysunek 5.9 przedstawia
przykład drzewa BST przed reorganizacją i po niej.

W rozwiązaniu tego zadania można zaproponować utworzenie nowego drzewa

przez pobranie z pierwszego kolejno elementów o największej wartości atrybutu,
tak aby znalazły się one jak najbliżej korzenia nowego drzewa BST.

W implementacji przewidziano trzy procedury pomocnicze:

1.  insert — wstawianie wierzchołka do drzewa BST,
2.  konstrBST - konstruowanie drzewa z danych w pliku input oraz
3.  max - poszukiwanie największego  elementu w dowolnym drzewie binar

nym.

Po utworzeniu nowego drzewa należy zwolnić pamięć zajmowaną przez pierw-

sze drzewo.

Algorytm reorganizacji drzewa BST

Dane: ciąg par liczb całkowitych, n - długość ciągu.

Wynik: nowe - korzeń nowego drzewa BST, po reorganizacji.

3. Poszukuj wierzchołków o kolejnej największej wartości atrybutu w pierwszym

drzewie BST i wykorzystując operację insert, wstawiaj je do nowego (zreorga
nizowanego) drzewa BST według pierwszego elementu pary.

4. Po wykorzystaniu kolejnego wierzchołka należy usunąć z niego informację

o atrybucie (w pierwszym drzewie), aby wierzchołek ten nie był ponownie
wybrany.

Złożoność: O(n), gdzie n jest długością ciągu.

Implementacja

type ref = ^elem;

elem = record a,b:integer; left, right:ref end;

procedure insert(x,y:integer; var trref); begin

if t = nil then

begin new(t);
with t^ do

begin a:=x; b:=y; left:=nil; right:=nil end

end else if x <> t^.a then

if x < t^.a then insert(x, y, t

.left)

else insert(x, y, t

.right)

end; { insert }

procedure konstrBST(n:integer; var t:ref);
var i:integer; begin

t: =nil ;
for i:=1 to n do

begin read(x, y); insert(x, y, t) end;

end; { konstrBST }

procedure max(t:ref; var mrinteger; var rrref);
begin

if t <> nil then

begin

if t^.b > m then begin m:=t^.b; r:=t end;
max(t^.left, m, r) ; max(t^.right, m, r) end; end; {
max }

procedure reorg(n:integer; var nowe:ref);
var m:integer; t,r:ref;

begin

konstrBST(n, t); nowe:=nil; m:=-l;
repeat

max (t, m, r) ;

r^.b:=-l;

if m <> -l then insert(r^.a, m, nowe);

until m = -1; end; { reorg }

5.3. Inne drzewa binarne

5.3.1. Konstruowanie drzewa dokładnie wyważonego

Drzewo dokładnie wyważone ma najmniejszą możliwą wysokość przy danej

liczbie wierzchołków. Na każdym poziomie liczba wierzchołków w jego
lewym i prawym poddrzewie różni się co najwyżej o jeden.

Na rysunku 5.10 przedstawiono dwa drzewa dokładnie wyważone na 4 i 10

wierzchołkach. Liczby wskazują kolejność wstawiania wierzchołków do drzewa.
Zauważmy, że wszystkie poziomy, z wyjątkiem ostatniego, są dokładnie zapełnio-
ne wierzchołkami. Natomiast na ostatnim poziomie mogą nie występować prawe
następniki wierzchołków poprzedniego poziomu.

W implementacji wykorzystano funkcję (por. [7]), która generuje elementy

struktury wskazywane przez lokalne wskaźniki i dołącza je do drzewa podczas
powrotu z rekurencji.

Rys. 5.10. Dwa drzewa dokładnie wyważone na « wierzchołkach (n = 4 i 10). Liczby wskazuj ą kolej-

ność wstawiania wierzchołków do drzewa

Algorytm konstruowania drzewa dokładnie wyważonego

Dane: n- liczba wierzchołków drzewa, z - zakres losowania elementów ciągu.

Wynik: drzewo dokładnie wyważone (binarne).

Metoda:

1.  Przeznacz j eden wierzchołek na korzeń.
2.  Zbuduj lewe poddrzewo z   nl = n div 2 wierzchołkami w niniejszy sposób.
3.  Zbuduj prawe poddrzewo z np = n-nl- l wierzchołkami.
Złożoność: O(n).

Rys. 5.11. Struktura danych i przykład drzewa dokładnie wyważonego (n = 4, z = 200)

type ref = ^elem;

elem = record a:integer; left, right:ref; end;

function DDW(n, z:integer):ref; { dane losowane }
var p:ref; x, nl, np:integer; begin

if n > 0 then

begin

nl:=n div 2; np:=n - nl - 1;
x:=random(z) + 1; write(out, x, ' ');
new(p); with p^ do begin

a:=x; left:=DDW(nl, z) ; right:=DDW(np, z);

end;

DDWl:=p;

end

else DDW:=nil;

end; { DDW }

5.3.2. Konstruowanie drzewa Wirtha

Przedstawimy prosty algorytm tworzenia drzewa binarnego z danych uporząd-

kowanych w preorder. Algorytm ten zaproponował N. Wirth i dlatego drzewo
generowane za pomocą tego algorytmu nazywamy drzewem Wirtha.

Jeżeli dany ciąg informacji jest uporządkowany w preorder (z wykorzystaniem

wyróżnionego symbolu,  np.  '*',  na  oznaczenie  braku  następnika),  to  w  najprost-
szym  przypadku  informację  mogą  stanowić  symbole  będące  literami,  tak  jak  w
implementacji algorytmu przedstawionego niżej. W przypadku ogólnym mogą to
być  np.  dowolne  identyfikatory.  Innym  zastosowaniem  tego  algorytmu  jest  kon-
struowanie  losowych  drzew  binarnych  wykorzystywanych  do  testowania  algoryt-
mów przetwarzania struktur drzewiastych.

W implementacji algorytmu Wirtha, w odróżnieniu od omówionych już algo-

rytmów konstruowania drzew binarnych, mamy tylko jedną procedurę rekurencyj-
ną  enter.  Działanie  tej  procedury  kończy  się,  gdy  ostatnio  pobrany  znak  będzie
przyjęty  jako  symbol  braku prawego  następnika  na skrajnej prawej ścieżce  budo-
wanego  drzewa.  Na  rysunku  5.12  podano  dwa  przykłady  drzewa  Wirtha  -  na
trzech i pięciu wierzchołkach (informację stanowią litery alfabetu łacińskiego).

a*bc***

*bc**cd*e***

Rys. 5.12. Dwa przykłady drzewa Wirtha wygenerowanego z danego ciągu znaków

Algorytm konstruowania drzewa Wirtha

Dane: ciąg liter i znaków '*' -wpreorder.
Wynik: drzewo Wirtha (binarne).
Metoda: Pobieraj kolejne elementy ciągu znaków. Jeżeli pobrano '*', to wskazy-
wane poddrzewo jest puste; w przeciwnym przypadku wygeneruj nowy wierzcho-

łęk, wstaw do niego pobraną informację i zbuduj w ten sam sposób jego lewe,
a następnie prawe poddrzewo.
Złożoność: O(n), gdzie n jest liczbą wierzchołków drzewa (liczbą liter w ciągu
wejściowym).

Implementacja

type ref=^elem;

elem=record a:char; left, right:ref end;

procedure enter(var t:ref); var chrchar; begin

read(ch); write(ch); if
ch = '*' then t:=nil else
begin

new (t); with
t

b e g i n a : = c h ; e n t e r ( l e f t ) ; e n t e r ( r i g h t ); e n d ; e n d ;

e n d; { ent er }

5.3.3. Kopce. Sortowanie przez kopcowanie

Drzewo binarne jest kopcem (ang. heap), jeżeli w każdym wierzchołku

przechowuje  informację  o  wartości  nie  mniejszej  niż  ta,  która  znajduje  się  w  jego
lewym  i  prawym  następniku.  Tak  więc,  jeżeli  w  kopcu  przechowywane  są  liczby
całkowite,  to  w  jego  korzeniu  znajduje  się  największa  liczba  spośród  wszystkich
występujących w tym kopcu.

Kopiec jest strukturą danych z bezpośrednim dostępem do największego

elementu,  czyli  jest  realizacją  kolejki  priorytetowej.  Pobieranie  informacji  z  tej
kolejki  polega  na  pobraniu  elementu  wskazywanego  przez  korzeń  kopca,
a  dokładanie  nowego  elementu  trzeba  tak  zaprojektować,  aby  nie  zniszczyć
struktury kopca.

Algorytm sortowania przez kopcowanie (por. [7], rozdz. 2.2.5) przetwarza

elementy tablicy  jednowymiarowej  tak,  jakby  były  elementami  drzewa  binarnego.
Pierwszy  element  tablicy  jest  korzeniem  tego  drzewa,  a  wszystkie  pozostałe
znajdują  się  na  kolejnych  poziomach.  Jeżeli  długość  ciągu  w  tablicy  jest  równa
całkowitej  potędze  liczby  2,  to  drzewo  binarne  jest  pełne,  w  przeciwnym
przypadku tylko ostatni poziom nie ma kompletu wierzchołków.

Jeżeli sortujemy ciąg o długości n w tablicy a, to następnikami elementu a, są

w drzewie elementy o indeksach 2i (lewy następnik) oraz 2i + l (prawy). Metoda

sortowania  przez  kopcowanie  jest  bardzo  prosta.  Najpierw  trzeba  utworzyć
pierwszy  kopiec  (czyli  ustawić  elementy  tablicy  tak,  aby  dla  każdego  /  wartość  a,
była  nie  mniejsza  niż  wartości  jego  następników).  Następnie  pierwszy  element
kopca (czyli a\) zamienia  się  miejsca mi  z  element em  ostatnim  (czyli  a„)
i  zmniejsza  długość  nie  posortowanego  ciągu  o  1.  Strukturę,  która  powstała  po
zamianie  elementów  tablicy,  należy  poprawić,  aby  znów  powstał  kopiec.  Dalsze
postępowanie jest podobne, czyli zamienia się wartości znajdujące się w a\ oraz na
końcu nie posortowanej części tablicy, czyli  a„-\. Po zakończeniu  operacji tablica
jest posortowana rosnąco.

Przedstawiamy dwie realizacje sortowania przez kopcowanie - z iteracyjnym

i rekurencyjnym poprawianiem kopca.

Na rysunkach 5.13 i 5.14 przedstawiono przykład czterech początkowych

kroków sortowania w tablicy a ciągu o długości 8 oraz odpowiadające im struktury
drzewa binarnego.

Rys. 5.13. Stany tablicy a w początkowych krokach sortowania, struktura drzewa i pierwszy kopiec

(2)

pierwszy kopiec

(3)

(4)

Rys. 5.14. Drzewo po pierwszej zamianie i drugi kopiec

Algorytm sortowania przez kopcowanie (iteracyjny)

Dane:
Wynik:
Metoda:
l . Utwórz pierwszy kopiec w tablicy a. 2.
Powtórz n -l razy następujące operacje:

a. zamień informację a[l] oraz a[i], zmniejsz wartość indeksu / o l,

utwórz nowy kopiec w nie posortowanej części tablicy: #[!],.., «[/].

Implementacja

const nmax = 100;
type ind = l..nmax;

t = array[ind] of integer;

{ a }

procedure heapsort(nr integer; var art);
var i,x r integer;

procedure popraw(j, last r integer); { iteracyjna }

var k,xr integer; b:Boolean;

begin

x:=a[j] ;
b:=false;

k:=2 * j;

drugi kopiec

: n - długość ciągu liczb, a - tablica zawierająca ciąg n liczb. ik:
a - tablica zawierająca posortowany (niemalejąco) ciąg n liczb

zame normacę a oraz a, zmnesz war o n

utwórz nowy kopiec w nie posortowanej części tablicy:

Złożoność: O(n log n).

while (k <= last) and not b do

begin

if k + 1 <= r then

if a[k + 1] > a[k] then k:=k + 1;

if a[k] > x

then begin a[j] :=a[k]; j:=k; k:=2 * j ; end
else b:=true

{ wyj

ście z pętli }

end;

a[j]:=x

end; { popraw }

begin { heapsort }

for i:=n div 2 downto 1 do popraw(i,n);
for i:=n downto 2 do begin

x:=a[i]; a[i]:=a[l]; a[l]:=x;
popraw(1, i - l); end; end; {
heapsort }

Algorytm sortowania przez kopcowanie (rekurencyjny)

Dane:  n - długość ciągu liczb, a - tablica zawierająca ciąg n liczb.
Wynik: a - tablica posortowana (niemalejąco).
Metoda:
1.  Utwórz pierwszy kopiec.
2.  Powtórz n - l razy:

zamianę miejscami korzenia kopca («[!]) i ostatniego elementu kopca oraz

b. utworzenie nowego kopca (algorytm rekurencyjny heapify) z ciągu krót

szego o l element.

Złożoność: O(n log n).

Implementacja

const nmax = 100;
type ind = 1..nmax;

t = array[ind] of integer;

{ a }

procedure heapsortl(n:integer; var a:t);
var i,x:integer;

procedure heapify(j,last:integer); { rekurencyjna}
var k,x:integer;
begin

if j <= last div 2 then

b e g i n

k:=2 * j;

i f k + l < = l a s t t h e n

if a [ k + 1] > a [ k] t he n k: = k + 1 ;

if a[ k] > a [ j ] t he n

b e g i n x : = a [j ]; a [ j ] : = a [ k ] ; a [ k]: = x ; en d ;

h e a p i f y ( k , l a s t ) ; e n d;

end; { hea pify }

b e g i n

f o r i: = n d i v 2 d o w n t o 1 d o h e a p i f y ( i ,n ) ; f o r
i:= n d o w nt o 2 do b e g i n

x : = a [ i ] ;       a [ i ] : = a [ 1 ] ;       a [ 1 ] : = x ;
h e a p i f y( l ,     i    -    1 ) ;   end;  e n d;    {
h e a p s ortl   }

5.4. Drzewa wielokierunkowe

5.4.1. Konstruowanie losowego drzewa wielokierunkowego

Rozważmy metodę tworzenia struktury drzewiastej, w której wierzchołki mogą

mieć dowolną liczbę następników (ograniczoną tylko przez liczbę wierzchołków
drzewa). Podobnie jak w przypadku wszystkich uprzednio rozważanych struktur,
przedstawimy metodę konstruowania losowego drzewa wielokierunkowego.

W metodzie wykorzystamy model losowego drzewa rekurencyjnego RRT

(ang. Random Recursive Tree) wprowadzony i badany teoretycznie przez Jerzego
Szymańskiego.

Metoda generowania drzewa RRT o n wierzchołkach jest prosta. Wierzchołek l

jest korzeniem  drzewa. Dla  każdego  następnego  wierzchołka  losujemy  (z  jednako-
wym  prawdopodobieństwem)  numer  wierzchołka,  który  będzie  jego  poprzedni-
kiem.  Tak  więc  poprzednikiem  wierzchołka  2  jest  zawsze  wierzchołek  l,  ale  dla
następnych  wierzchołków  wybór  jest  coraz  większy.  Wyniki  losowania  przecho-
wujemy w ciągu a, (/ = l, 2, ..., n). W podobny sposób generujemy drzewo RRT
o  zadanym  ciągu  stopni  wierzchołków:  po  wylosowaniu  poprzednika  sprawdzamy,
czy  może  być  on  zaakceptowany  (jeśli  nie,  losujemy  ponownie).  Na  rysunku  5.15
przedstawiono  przykład  losowego  drzewa  wielokierunkowego  o  pięciu  wierzchoł-
kach.

Algorytm konstruowania drzewa wielokierunkowego

Dane: n - liczba wierzchołków.

Wynik: t - korzeń losowego drzewa wielokierunkowego.

Metoda:

Wygeneruj drzewo w tablicy a w następujący sposób:

wierzchołek l nie ma poprzednika,

losuj poprzedniki dla wierzchołków od 2 do n (spośród liczb od l do z - l
w każdym kroku i z jednakowym prawdopodobieństwem).

Wyniki zapisz w tablicy list L.

Złożoność: O(n).

Rys. 5.15. Przykład drzewa wielokierunkowego, n = 5

Implementacja

const nmax=100;
type ind=l..nmax;
ref

elem;

elem=record a: integer; x: Boolean; son:ref;

next:ref end;
ta=array [ind] of integer;

{ a }

tL=array [ind] of ref;

{

}

procedure konstrRRT (n: integer; var t:ref);

{ K. Zwierzy

ński, Inf. 1998 }

var a:ta; L:tL; i : integer;

procedure generacja (n: integer; var a:ta);
var i : integer;
begin

a[l]:=0; for i:=2 to n do a [i] :=random(i-l) + 1;

end; { generacja }

procedure initL(n:integer; var L:TL);
var i:integer;
begin

for i:=l to n do
begin new(L[i]) ;

with L[i]^ do begin a:=i;son:=nil;next:=nil end;

end;

end; { initL }

begin { konstrRRT }

generacja(n, a); initL(n, L) ;
for i:=n downto 2 do begin

L[i] ^.next:=L[a[i]]^.son;
L[a[i]]^.son:=L[i]; end;

t:=L[l];

{ korze

ń drzewa wielokierunkowego }

end; { konstrRRT }

Na rysunku 5.16 przedstawiono strukturę danych - element listy następników

każdego wierzchołka oraz drzewo z poprzedniego rysunku w strukturze danych.
Aby ułatwić dostęp do każdego wierzchołka, przewidziano tablicę L zawierającą
wskaźniki wierzchołków.

Rys. 5.16. Przykład struktury danych dla drzewa wielokierunkowego z poprzedniego rysunku