43 (478)

Gdyby ktoś był zainteresowany złożonością to należy zwrócić uwagę,-że wnosi on 0(m-nj. Wynika to z fair:uu że każdy wierzchołek umieszczany i usuwany z kolejki jest jeden raz, a liczba obrotów pętli for w procedurze WSZERZ jest oczywiście rzędu liczby krawędzi' grafu.

Metodę przeszukiwania wszerz można stosować do poszukiwania najkrótszej drogi między dwoma wierzchołkami liczoną ilością zawartych w sobie krawędzi. Sposób ten przedstawia poniższy algorytm:

va.r

nrerl:    Arr*y[1 . .

odl : array[l.

rin i    riri.

i ’ j J w *■ ^A ♦ • ♦ l ^ł ; •

.[V]] of integer

wierechołki poprzedzajace na najkrótszej drodze} (długość najkrótszej drogi}

begin

for ueV'do

nowy(vj:-erue; [ inicjujemy wierzchołki w grafie} end for;

kciejka: -pusca_kole jka; („zerujemy" kolejkę)

kolejka <*v_;;

r.cwy (v._:} : - fslse;

cred(v.J:=-1;

odi(v,i : = 0;

while nowy{x] do

o < = kolejka; (jest aktualnym „pop r ze ćn ik i e r" w kolejce* for ueadj [p] dc    o-dj [“pi '

if ncv/yfuj then

kolejki < = n; nowy(u]:= f a15 e ; pred(u; :=p.; odl[uJ:-odl(p} -1; end. if; end for; end while; end {progran).

Dla powyższego algorytmu i jeszcze wyższego grafu można przeprowadzić analizę jego działania. Znajdźmy więc najkrótszą drogę z wierzchołka (I) do (7). Program zaczyna umieszczać w kolejce wierzchołki w rosnącej odległości od wierzchołka stanowego. Czyli na początku wierzchołek stanowy v„ czyli (1), porem (2) i (5), Gęśli lista incydencji wierzchołków uporządkowana jest rosnąco), następnie (5), (6) i (7). Pętla while kończy pracę gdy wierzchołek przeznaczenia ma status falsc, a dzieje się to w. luumcuCić umieszczenia go w kolejce i obliczenia jego odległości od wierzchołka stanowego. Tablica oJI[aJ zawiera właśnie tą odległość. Zaletą algorytmu jest koniec pracy w momencie znalezienia najkrótszej drogi. Jak wszyscy się domyślają odległość z wierzchołka (1) do (7) liczoną ilością krawędzi włączonych do drogi jest.... no, no.... 2. Ale ładnie !

57. Fuuać i oniówić uigo/ylti) Zńiajdow&itid cykli fundBmer.isInych w grdfis. Jeke jestyoo-zlozon ość 7

PmdsićTATny najpierw algorytm: beęin

fer x = V do

nusi[xJ:=C;(inicjacja numeracji vierzchcłko«} end for;

" ■ i' ^ /»łni v rmmarjr-i odv/ i sć z SP- ych kclsjnych wisrzcheikćw w dĄd}

=0;(licznik cykli fundamentalnych }

*0;{wskaźnik stosu } for x£ V do ^

if r.un{x] = 0 then k:-krl; stos {k) : *=x;

ZNAJDŹ(x, 0);

end if; end for; end {prógran);