5032124665

22

I. PROJEKTOWANIE I ANALIZA ALGORYTMÓW

{4}    end

end

end; {greedy}

Zredukowaliśmy tym samym nasz algorytm do zbioru operacji wykonywanych na dwóch zbiorach wierzchołków. Pętla zewnętrzna (wiersze od {2} do {5}) stanowi iterację po niepokolo-rowanych wierzchołkach grafu 6; pętla wewnętrzna (wiersze od {3.2} do {3.4}) iteruje natomiast po wierzchołkach znajdujących się aktualnie w zbiorze newclr. Instrukcja w wierszu {5} dodaje nowy wierzchołek do zbioru newclr.

Język Pascal oferuje wiele możliwości reprezentowania zbiorów danych — niektórymi z nich zajmiemy się dokładniej w rozdziałach 4. i 5. Na potrzeby reprezentowania zbioru wierzchołków w naszym przykładzie wykorzystamy inny abstrakcyjny typ danych, LIST, który może być zaimplementowany jako lista liczb całkowitych (integer), zakończona specjalną wartością nul 1 (która może być reprezentowana przez wartość 0). Lista ta może mieć postać tablicy, lecz — jak zobaczymy w rozdziale 2. — istnieje wiele innych sposobów jej reprezentowania.

Zastąpmy instrukcję for w wierszu 3.2 na listingu 1.2 przez pętlę, w której zmienna w reprezentuje kolejne wierzchołki zbioru newclr (w kolejnych obrotach pętli). Identycznemu zabiegowi poddamy pętlę rozpoczynającą się w wierszu {2}. W rezultacie otrzymamy nową, bardziej precyzyjną wersję procedury, która zaprezentowana jest na listingu 1.3.

LISTING 1.3.

Kolejny etap sprecyzowania procedury greedy

procedurę greedy (var G: GRAPH; var newclr: LIST);

{ greedy zapisuje w newclr zbiór wierzchołków, którym należy przyporządkować ten sam kolor } var

found : boolean; v. w : integer; begin

newclr : = 0;

v ;= <pierwszy niepokolorowany wierzchołek w grafie G>; while v <> nuli do begin found : = false;

w := <pierwszy wierzchołek ze zbioru newclr>; while w <> nuli do begin

if <istnieje w grafie G krawędź łącząca wierzchołki v i w> then found := true;

w := <następny wierzchołek ze zbioru newclr>;

end;

if found = false do begin oznacz v jako pokolorowany; dodaj v do newclr

end;

i/ := <następny niepokolorowany wierzchołek w grafie G>; end

end; { greedy }

Procedurze pokazanej na listingu 1.3 sporo jeszcze brakuje do tego, by została zaakceptowana przez kompilator Pascala. Poprzestaniemy jednak na tym etapie jej precyzowania, gdyż chodzi nam raczej o prezentację określonego sposobu postępowania niż ostateczny wynik. □