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.
Wyni 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;
int eger;
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 }
Przykład. Po wywołaniu funkcji .y:=min(w, d) dla danych z poprzedniego przykł;
du zmienna y będzie miała wartość 8.
13
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(n2) do O(nlogn). Opis kilku najważniejszych można znalez
ć
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' od l do n - l znajdz
najlepszy element (najmniejszy, jeśli
sortujemy rosnąco) w nie posortowanej części tablicy, zamień go z elementem a[/].
Złożoność: O(n2).
Implementacja
const nmax =100; type
ind = l..nmax;
t = array[ind] of integer; { a }
procedure sort( n:i nt eger; var a : t ) ;
va r i , j , k: i nt e ger ; na j : i nt e ger ; begi n
for i:=l to n - 1 do
begi 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 { zamień }
; a[k] :=a[i]; a[i]
:=naj; end; end; {
i } { sort }
14
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
const nmax = 100;
type ind = L. nmax;
t = array[ind] of integer; { a }
funct i on su ma( n:i nt eger; var a:t):i nte ger;
var i: i nt eger ; s: i nt eger ; begi n
s: =0;
for i:=l t o n do s: =s + a[i];
suma:=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?".
15
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;
while (i <= n) and not jest do
if a[i] = x t hen j est: =true else i: =i + 1;
member: =jest;
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ędz
, 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ędz
(i, f). Największą liczbę
krawędzi na n wierzchołkach, czyli \E\ = n(n - l)/2, ma graf Kn, 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),
16
w którym rozważa się niezależnie każdą krawędz
grafu pełnego Kn 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ędz
(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ędz
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):
a. wylosuj liczbę z przedziału (O, 1),
b. jeśli ta liczba jest nie większa niż p, to dodaj krawędz
(i, j) do grafu G,
c. uzupełnij informację o krawędzi (j, i) w tablicy A.
Złożoność: O(n2).
Implementacja
Boolean
Rys. 2.2. Tablica kwadratowa o elementach typu logicznego do reprezentacji grafu
17
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: l2
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ędz
, 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.
18
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:
a. 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
c. zmniejsz h o 1.
Złożoność: O(n2).
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 }
19
for i:=l to n - 1 do for
j : =i + 1 to n do begi n
h:=h + 1; { powiększenie indeksu }
with E[ h] do begin a:=i; b:=j end; { krawędz
}
end;
t ot al : =h; { liczba wszystkich krawędzi, n(n-l)/ 2 }
end; { init }
procedure Gnk( n, k, t ot al:i nt eger; var E : t 1 ) ;
var i , h, z: i nt e ger ; x: r ;
begin
h: =t ot al ; for i:=l
to k do begi n
z:=random(h) + 1 ; { losowanie indeksu tablicy E }
x:=E[z]; E[ z ] : = E[ h] ; E[h]:=x;{ zamiana }
h:=h - 1; { zmniejszenie przedziału losowania } end;
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(n2).
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 }
21
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 }
22
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
const nmax = 100; t ype
el e m = l.. nmax;
zbi ór = set of el e m;
pr oce dure dr ukz bi or( fi r st:i nt eger ; w:z bi or) ;
var x: ele m; begi n
x: =f i r s t ; while w
<> [] do begi n
if x in w then
begi n
write(out, x: 3, ' , ' ) ;
w:=w - [x] end;
x:=x + 1; end; end;
{ drukzbior }
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
23
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 , sprawdz
, 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(n2).
Implementacja
Rys. 2.6. Struktury danych w implementacji algorytmu transformacji A > S reprezentacji
grafu G
24
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 StS) ;
var i,j:integer;
begin
for i:=l to n do with S[i] do begin w:=[];
l:=0; end;
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
1; end;
S[j] do begin w:=w + [i]; 1:=1 + end; end; {
1; end;
transAS }
Przykład. Reprezentacja grafu G w tablicy S
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
25
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(n2).
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
26
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 sprawdz
, 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(n3).
27
Implementacja
const nmax = 100;
type ind = l..nmax;
t2 = array[ind, i nd] of Boolean;{ A }
functi on t ri angl es(n:i nt eger; var A: t2) :i nt eger;
var i, j , h: i nt eger ; x: i nt eger ;
beginx:=0;for i:=l to n - 2
do for j:=i + 1 to n
do
i f A[ i, j] t he n
if A[i, h] and A[j, h]
then x: =x +1;
triangles : =x
end; { triangles }
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(n4). W drugim algorytmie wykorzystano inny po-
mysł - zmniejszono złożoność obliczeniową do O(n3).
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. sprawdz
, 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
const nmax = 100; type
ind = l..nmax;
t2 = array[ind,ind] of Boolean; { A }
28
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(n3).
Implementacja
functi on cykl 4TF( n:i nt eger; var A:t 2):l ongi nt;
{ Tomasz Fitzermann, EiT Ir., 1998 )
var i , j, k: i nt eger ; c, x: l ongi nt ; begi n x:=0; if n >= 4
then
for i:=1 to n - l do for
j:=i + l to n do begi n
c:=0; for k:=i + l to n do
if A[i, k] and A[j, k] then c:=c + 1; if c
>= 2 then x:=x + c*(c - 1) div 2; end;
cykl4TF:=x; end;
{ cykl4TF }
29
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
30
BooleanintegerBoolean
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;
31
f or v: =r t o n do
if A[ w, v] then OnCycle(d + 1, v, r); if
d = 2 then begi n
i: =m[ 1]; j: =m[ 2]; A[ i , j ] : =f a l s e ;
A[ j , i ] : =f al s e; Deg[i]:=Deg[i] -
1; Deg[j] :=Deg[j] - 1; end; { if d
} m[ d] : =- !; x[ w] : =f al s e; end; {
else } end; { if not } end; { else
} end; { OnCycle }
begin { Cycles }
h:=0;
if c >= 3 then
begi n
for i: =1 to n do
begi n
x[ i ] : =f al s e;
m[ i ] : =- 1;
Deg[i]: =0 end;
for i:=l to n - 1 do
for j:=i + 1 to n do
if A [i, j ] t hen begi n
Deg[i]:=Deg[i] + 1;
Deg[j]:=Deg[j] + 1;
end;
for i:=l to n - c + 1 do OnCycle(1, i, i ) ;
end;
Cycles:=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 znalez
ć 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 }
33
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 ype pli k = fi l e of i nt eger;
pr ocedur e dr ukpl i k( var p: pli k; var out:t ext );
var x:i nt eger;
begin
begin read(p, x); write(out, x); end;
cl ose(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.
34
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. A
ą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 ype pl i k = fi l e of i nt e ger ;
pr ocedur e mer ge( var f, g: pli k; var h:pl i k) ;
var b: Bool ean;
be gi n
35
reset (f); reset (g); rewrite (h) ;
b:=eof (f) or eof (g)/
while not b do
begin
if f ^ < g^
then
end
begin h^ : =f ^; get(f); b:=eof(f);
else
,__
begin h^ :=g ^; get(g); b:eof(g);
end;
put(h) ;
get(f) end; get(g) end; close(f); close(g); close(h);
end; { merge }
end;
while not eof (f) dobegin h^:=f^; put(h)
while not eof (g) dobegin 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
36
wartości wszystkich możliwych ciągów dla danej struktury. Na przykład, ciąg ka
noniczny grafu G = P4 (ś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(n2).
Implementacja
Struktury danych przedstawiono na rys. 3.1.
37
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 }
38
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 ;
for j:=l to n do if A[i,j] then s := s + 1;
De g[ i ]: =s; DegSor t [i]: =s; end;
sort( n, DegSort); end;
end; { j eden }
3.2.3. Konstruowanie pliku grafów samodopełniających
Każdemu grafowi G o n wierzchołkach i k krawędziach odpowiada graf Gc, 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 Gc,
3. sprawdzenie, czy grafy G i Gc są izomorficzne, i jeśli tak, to zapamiętan
jednego z nich w pliku sc grafów.
39
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 Kn 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 ;
type ind = l..nmax; ind1 = 1..kmax;
r = recor d a, b: i nt eger end;
tl = array [indl] of r;{ E }
t2 = array[ind,ind] of Boolean; { A }
13 = array[ind] of byte;{ Deg, DegSort }
TGraph = record A:t2; Deg, DegSort:t3 end;
plik = file of TGraph;
40
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
41
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 ype pl i k = fi l e of TGr a ph;
pr ocedur e pr zesi e wa ni e( n, g: i nt eger ; var W, Z: pl i k;
var s c: i nt eger );
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 }
42
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=0m=lm=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 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ędz
jest losowana z jednakowym prawdopodobieństwem ze
zbioru
wszystkich dostępnych krawędzi,
2. wylosowaną krawędz
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ędz
, 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.
43
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ędz
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(n2).
Implementacja
44
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ć wskaz
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 wskaz
nikowa p ma wartość adresu począt-
ku tego obszaru w pamięci. Zmienna wskazywana przez zmienną wskaz
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 }
46
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 }
47
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ć wskaz
nik na kolejny
element dopóki będzie on miał wartość różną od wskaz
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.
48
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 wskaz
niki.
Zachęcamy do zaprojektowania algorytmu sortowania listy z zamianą wskaz
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ą wskaz
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ń wskaz
nik h na następny element listy.
Złożoność: O(n2).
49
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 wskaz
nika nil do pola wskaz
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 wyprowadz
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^. next ;
p^. ne xt : =ni l ;
di s pos e( p) ; end; end;
{ pop }
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 wskaz
-
nik początku listy, ale potrzebny jest również wskaz
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);
with p-^ do begin a:=x; next:=nil; end; if h
<> nil then s^. next; =p else h: =p; s: =p ; end;
{ into }
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
type ref = ^elem;
el e m = recor d a: i nt eger; next : r ef; end;
pr oce dur e i ns er t ( K: i nt eger ; var h: r ef) ;
begi n
if (h = nil) or (x < h^.a) then push(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.
52
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, Qm - 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:
a. wygeneruj graf losowy G = G(n, f),
b. oblicz m - liczbę wierzchołków nienasyconych w G,
c. zwiększ Qmo1,
d. przepisz graf G z tablicy E do rekordu typu TGraph,
e. dopisz graf do poczÄ…tku listy.
Złożoność: O(n2).
Implementacja
const nmax = 13; kmax = nmax*(nmax - 1) di v 2;
type ind = 1.nmax; indl = L.kmax;
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
53
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. Sprawdz
, 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)
54
Implementacja
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 }
55
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 }
56
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, hA.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 }
57
4.3. Lista wielopoziomowa
4.3.1. Konstruowanie listy list identyfikatorów
Skorowidz zrealizowany jako lista list zawiera wskaz
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:
a. pobierz x - kolejny identyfikator,
b. sprawdz
, gdzie na liście H znajduje się litera równa pierwszej literze w x,
c. 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;
d. w przeciwnym przypadku sprawdz
, 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 =15; { 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 }
58
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).
59
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 ct 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
60
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:
a. 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ędz
równoległa), to powtórz losowanie krawędzi od po
czÄ…tku, ale dla ostatnio uzyskanego stanu tablicy L;
b. w przeciwnym przypadku wylosowany element tablicy L zamień miejsca
mi z elementem poprzedzającym ten, dla którego wykonano losowanie,
i dodaj nową krawędz
do grafu G (zaktualizuj zbiór krawędzi).
Złożoność: O(n5).
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 }
61
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-
62
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 c3 - liczbÄ™ trójkÄ…tów w G,
b. sprawdz
, gdzie na liście wartości niezmiennika znajduje się wartość c3,
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 CT, znajduje się na liście H, to sprawdz
, czy graf G jest izomorficzny z
jakimś elementem listy i jeśli odpowiedz
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 znalez
ć 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.
63
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).
Rys. 4.5. Przykład struktury tablicy mieszającej
Implementacja
64
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 }
65
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. Sprawdz
, 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 poddrzewoprawe poddrzewo
Rys. 5.1. Struktura drzewa binarnego
67
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 wskaz
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
68
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 }
69
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 znalez
ć 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. odwiedz
korzeń t, odwiedz
jego lewe poddrzewo w ten sam sposób,
odwiedz
jego prawe poddrzewo w ten sam sposób,
2. inorder: odwiedz
lewe poddrzewo wierzchołka t, następnie wierzchołek / oraz
prawe poddrzewo wierzchołka t,
3. postorder: odwiedz
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
type ref = ^elem;
ele m = record a: i nt eger; left, ri ght: ref e nd;
procedure preor der (t : ref ); begi n
if t <> nil then
begi n
write (out, t^.a, ' ' ) ;
pr eor der (t^. l eft ) ; preor der
(t^ . ri ght) ; end;
end; { preorder } procedure
inor der (t : ref ); begi n
if t O nil then
begi n
i nor der (t^. l ef t ) ; write
(out, t^.a, ' ' ) ; i nor der (t^
.ri ght ) ; end;
end; { inorder } procedure
post or der ( t : ref ); begi n
if t <> nil then
begi n
post or der (t^ . l eft) ; postorder ( t^
. right ) ; write (out, t^.a, ' ' ) ;
end; end; { postorder }
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.
71
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łaszczyz
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  *".
72
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,1 '); writeln(out,a);
druk3(left, h + 3); end; end; { druk3
}
73
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-
74
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 tA 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 }
75
5.1.6. Poszukiwanie największego elementu w drzewie
Jeżeli należy znalez
ć 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 }
76
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 odpowiedz
jest  tak". Jeśli jedno
z nich jest puste, to odpowiedz
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 sprawdz
, 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 }
77
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:
a. 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).
78
Implementacja
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 }
79
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
prowadz
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 = Aelem;
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:=tA.left
else t:=tA.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 }
80
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 nil then
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).
81
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 sprawdz
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 (Å‚ub najmniejszy w prawym poddrzewie), wstaw tÄ™ informacjÄ™
zamiast x i usuń znaleziony wierzchołek.
2. Zwolnij pamięć, którą zajmował usunięty wierzchołek.
Złożoność: O(n), gdzie n jest liczbą elementów drzewa
82
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 wskaz
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 sprawdz
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;
83
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:=tA.right
else begin
szukajprawego(tA.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.
84
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.
85
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.
86
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, tA.left)
else insert(x, y, tA.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;
87
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 wskaz
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
88
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 }
89
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***
a
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-
90
łę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
tA do
begi n a: =ch; ent er(l eft ); ent er(ri ght ); end; end;
end; { enter }
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
91
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Ä™ miejscami z elementem 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.
(2)
pierwszy kopiec
Rys. 5.13. Stany tablicy a w poczÄ…tkowych krokach sortowania, struktura drzewa i pierwszy kopiec
92
(3) (4)
drugi kopiec
Rys. 5.14. Drzewo po pierwszej zamianie i drugi kopiec
Algorytm sortowania przez kopcowanie (iteracyjny)
: 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
Dane:
Wynik:
Metoda:
l . Utwórz pierwszy kopiec w tablicy a. 2.
Powtórz n -l razy następujące operacje:
a. zame normacÄ™ a oraz a, zmnesz waro n
b. utwórz nowy kopiec w nie posortowanej części tablicy:
Złożoność: O(n log n).
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;
93
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:
a. 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
94
begi n
k:=2 * j;
if k + l <= last then
if a[k + 1] > a[k] then k:=k + 1;
if a[k] > a [ j ] then
begin x:=a[j]; a [ j ] : = a [ k ] ; a[k]:=x; end;
heapif y( k, last ); end;
end; { heapify }
begi n
for i:=n div 2 downt o 1 do heapify(i,n); for
i:=n downto 2 do begi n
x: =a[i]; a[i]: =a[1]; a[1]: =x;
heapify( l , i - 1); end; end; {
heapsortl }
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.
95
Algorytm konstruowania drzewa wielokierunkowego
Dane: n - liczba wierzchołków.
Wynik: t - korzeń losowego drzewa wielokierunkowego.
Metoda:
1. Wygeneruj drzewo w tablicy a w następujący sposób:
a. wierzchołek l nie ma poprzednika,
b. 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).
2. Wyniki zapisz w tablicy list L.
Złożoność: O(n).
t
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;{ L }
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 }
96
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ą
wskaz
niki wierzchołków.
Rys. 5.16. Przykład struktury danych dla drzewa wielokierunkowego z poprzedniego rysunku