k balinska projektowanie algorytmow i struktur 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.

Rys. 5.9. Przykład reorganizacji drzewa BST

Metoda:

1. Utwórz pierwsze drzewo BST z ciągu par liczb całkowitych według pierwsze

go elementu pary.

2. Przygotuj nowe drzewo BST.

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