5032124664

21

1.1. OD PROBLEM U DO PROGRAMU

{2}    for <v reprezentujący każdy niepokolorowany jeszcze wierzchołek w G> do

{3}    if <v nie jest połączony krawędzią z żadnym wierzchołkiem wchodzącym

w skład newclr > then begin {4}    oznacz v jako pokolorowany;

{5}    dodaj v do newclr

end

end; {greedy}

Na listingu 1.1 widoczne są podstawowe elementy zapisu algorytmu w pseudojęzyku. Po pierwsze, widzimy zapisane tłustym drukiem i małymi literami słowa kluczowe, które odpowiadają zastrzeżonym słowom języka Pascal. Po drugie, słowa pisane w całości wielkimi literami — GRAPH i SET³ są nazwami abstrakcyjnych typów danych. W procesie stopniowego precyzowania typy te muszą zostać zdefiniowane w postaci typów danych pascalowych oraz procedur wykonujących na tych danych określone operacje. Abstrakcyjnymi typami danych zajmiemy się szczegółowo w dwóch następnych punktach.

Konstrukcje strukturalne Pascala, jak: if, for i while są użyte w naszym pseudojęzyku w oryginalnej postaci, jednakże już np. warunek w instrukcji if (w wierszu {3}) zapisany jest w sposób zupełnie nieformalny, podobnie zresztą jak wyrażenie stojące po prawej stronie instrukcji przypisania w wierszu {1}. Nieformalnie został także zapisany zbiór, po którym iterację przeprowadza instrukcja for w wierszu {2}.

Nie będziemy szczegółowo opisywać procesu przekształcania przedstawionej procedury do poprawnego programu pascalowego, zaprezentujemy jedynie transformację instrukcji if z wiersza {3} do bardziej precyzyjnej postaci.

Aby określić, czy dany wierzchołek v połączony jest krawędzią z którymś z wierzchołków należących do zbioru newclr, rozpatrzymy każdy element w tego zbioru i będziemy sprawdzać, czy w grafie G istnieje krawędź łącząca wierzchołki v oraz w. Wynik sprawdzenia zapisywać będziemy w zmiennej boolowskiej found — jeśli rzeczona krawędź istnieje, zmiennej tej nadana zostanie wartość true.

Zmieniona wersja procedury przedstawiona została na listingu 1.2.

LISTING 1.2.

Rezultat częściowego sprecyzowania procedury greedy

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

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

{1}    newclr : = 0;

{2}    for <v reprezentujący każdy niepokolorwany jeszcze wierzchołek w G>

do begin

{3.1}    found := false;

{3.2}    for <w reprezentującego każdy wierzchołek w zbiorze newclr> do

{3.3}    if <istnieje w grafie G krawędź łącząca wierzchołki v i w> then

{3.4}    found := true;

{3.5}    if found = false then begin

{ v nie łączy się z żadnym wierzchołkiem ze zbioru newclr }

{4}    oznacz v jako pokolorowany;

{5}    dodaj v do newclr

Odróżniamy tu abstrakcyjny typ danych SET od typu zbiorowego set języka Pascal.