Pseudokody do wyk ladu 6

31 marzec 2011

Problem otoczki wypuk lej

Otoczka wypuk la zbioru punkt´

ow Q,

|Q| ≥ 3, to najmniejszy

wieloka

,

t wypuk ly P taki, ˙ze ka˙zdy punkt ze zbioru Q le˙zy albo

na brzegu P albo w jego wne

,

trzu

Algorytm: (Grahama)

– niech p

0

be

,

dzie punktem w Q o minimalnej wsp´

o lrze

,

dnej y

(lub w przypadku remisu, pierwszym takim punktem z lewej

strony)

– niech (p

1

, p

2

, . . . , p

m

) be

,

da

,

pozosta lymi punktami Q

posortowanymi ze wzgle

,

du na wsp´

o lrze

,

dna

,

ka

,

towa

,

wzgle

,

dem

p

0

w kierunku przeciwnym do ruch wskaz´

owek zegara; je´

sli

wie

,

cej ni˙z jeden punkt ma taka

,

sama

,

wsp´

o lrze

,

dna

,

ka

,

towa

,

,

usu´

n wszystkie opr´

ocz po lo˙zonego najdalej od p

0

Wsp´

o lrze

,

dna ka

,

towa punktu p

i

wzgle

,

dem punktu pocza

,

tkowego

p

0

, to ka

,

t wektora p

i

− p

0

w biegunowym uk ladzie wsp´

o lrze

,

dnych

Typeset by

AMS-TEX

1

2

– od l´

o˙z pierwsze trzy punkty na stos S

PUSH (S, p

0

)

PUSH (S, p

1

)

PUSH (S, p

2

)

– stos S zawiera kandydat´

ow na wierzcho lki otoczki; ka˙zdy

punkt z wej´

sciowego zbioru Q jest raz wk ladany na stos,

a punkty nie be

,

da

,

ce wierzcho lkami otoczki sa

,

w ko´

ncu

ze stosu zdejmowane

for i

← 3 to m

do while ka

,

t utworzony przez punkty NEXT-TO-TOP (S),

TOP (S) i p

i

nie stanowi skre

,

tu w lewo

do POP (S)

PUSH(S, p

i

)

gdzie funkcja NEXT-TO-TOP(S) zwraca element po lo˙zony o jedno
miejsce poni˙zej szczytu stosu, bez zmiany stosu S

– po zako´

nczeniu algorytmu stos S zawiera wy la

,

cznie

wierzcho lki otoczki w przeciwnej do ruch wskaz´

owek

zegara kolejno´

sci ich wyste

,

powania na brzegu

return S

3

Przeszukiwanie grafu wszerz

Dany jest graf G = (V, E) wraz z wyr´

o˙znionym wierzcho lkiem s,

zwanym ´

zr´

od lem

Badamy krawe

,

dzie grafu G w celu znalezienia ka˙zdego wierzcho lka,

kt´

ory jest osia

,

galny z s

Przy okazji obliczamy odleg lo´

s´

c (najmniejsza liczba krawe

,

dzi) od

´

zr´

od la s do wszystkich osia

,

galnych wierzcho lk´

ow

W konsekwencji mo˙zna otrzyma´

c drzewo (przeszukiwania wszerz)

o korzeniu w s, kt´

ore zawiera wszystkie osia

,

galne wierzcho lki grafu

Zasada przeszukiwania wszerz: wierzcho lki w odleg lo´

sci k od

´

zr´

od la sa

,

odwiedzane przed wierzcho lkami w odleg lo´

sci k + 1

Idea algorytmu

* graf G = (V, E) jest reprezentowany za pomoca

,

listy sa

,

siedztwa.

Niech dla ka˙zdego u

∈ V elementami A[u] sa

,

wszystkie

wierzcho lki v takie , ˙ze

{u, v} ∈ E, tj. A[u] ,,sk lada” sie

,

ze

wszystkich wierzcho lk´

ow sa

,

siaduja

,

cych z u w grafie G

* z ka˙zdym wierzcho lkiem zwia

,

zane sa

,

naste

,

puja

,

ce zmienne

kolor[u] – zapamie

,

tuje kolor wierzcho lka u

p[u] – zapamie

,

tuje poprzednika wierzcho lka u

d[u] – odleg lo´

s´

c od korzenia s (´

zr´

od la) do wierzcho lka u

* pocza

,

tkowo wszystkie wierzcho lki (z wyja

,

tkiem s) sa

,

bia le

for ka˙zdy u

∈ V \ {s}

do kolor[u]

← bia ly

d[u]

← ∞

p[u]

← NIL

4

ponadto

kolor[s]

← szary

d[s]

← 0

p[s]

← NIL

* ka˙zdy nowo napotkany wierzcho lek staje sie

,

odwiedzony

a jego kolor staje sie

,

szary (potem czarny); wierzcho lki

szare sa

,

wierzchokami odwiedzonymi, kt´

orych listy sa

,

siedztwa

nie zosta ly jeszcze w ca lo´

sci przejrzane

* wierzcho lki szare pamie

,

tane sa

,

w kolejce Q typu FIFO

Q

← ∅

ENQUEUE(Q, s)

* dop´

oki kolejka nie jest pusta, badamy sa

,

siad´

ow pierwszego

elementu kolejki (nale˙zy go usuna

,

´

c z kolejki): je˙zeli jego

sa

,

siad, powiedzmy v nie by l jeszcze odwiedzony to

kolorujemy go na szaro, uaktualniamy warto´

sci wektor´

ow d[v],

p[v] i wstawiamy go do kolejki

while Q

̸= ∅

do u

← DEQUEUE(Q)

for ka˙zdy v

∈ A[u]

do if kolor[v] = bia ly

then kolor[v]

← szary

d[v]

← d[u] + 1

p[v]

← u

ENQUEUE(Q, v)

* kiedy wszystkie wierzcho lki z listy sa

,

siedztwa wierzcho lka u

sa

,

ju˙z przeanalizowane, to u jest kolorowany na czarno

kolor[u]

←czarny

5

Algorytm: (BFS – Breadth-First Searching)

BFS(G, s)

for ka˙zdy u

∈ V \ {s}

do kolor[u]

← bia ly

d[u]

← ∞

p[u]

← NIL

kolor[s]

← szary

d[s]

← 0

p[s]

← NIL

Q

← ∅

ENQUEUE(Q, s)
while Q

̸= ∅

do u

← DEQUEUE(Q)

for ka˙zdy v

∈ A[u]

do if kolor[v] = bia ly

then kolor[v]

← szary

d[v]

← d[u] + 1

p[v]

← u

ENQUEUE(Q, v)

kolor[u]

←czarny

SCIEZKA (G, s, v)

if v = s

then wypisz s
else if p[v] = NIL

then wypisz ,,nie ma ´

scie˙zki od s do v”

else SCIEZKA (G, s, p[v])

wypisz v