ALG&0

260 Rozdział 10. Elementy algorytmiki grafów

przebadane podczas przeszukiwania. Dopiero potem algorytm weźmie pod uwagy listy wierzchołków przyległych, wierzchołków już przebadanych: (0, 2, Ą (O, 4, 6) i (0, I, 3. 5). W konsekwencji, kolejność przeszukiwania grafu z rysunku 10 - 11, będzie taka: 0, J, 3, -I, 2, 6 i 5.

Jak jednak zapamiętać, podczas przeszukiwania danego wierzchołka /, że mamy jeszcze ewentualne inne wierzchołki czekające na przebadanie? Okazuje się, że najlepiej jest do tego wykorzystać zwykłą kolejki;', która „sprawiedliwie” obsłuży wszystkie wierzchołki, zgodnie z kolejnością ich wchodzenia do kolejki (poczekalni).

Zawartość kolejki dla naszego przykładu przedstawiać się będzie zatem w ten

sposób:

Rys 10 - 12.

Zawartość kolejki podczas przeszli kiwania grafu wszerz

zawartość

0 O 0    0

©©©©0000

_©000©0©©0© _

--------------► etap

Algorytm przeszukiwania „wszerz”. zapisany w C++. przedstawia się następująco:

breadthf.cpp

void szukaj(int G[n][n],int V[n],int i)

// rozpoczynamy od wierzchołka 'i¹ // G - graf nxn

// V przechowuje informacje/ czy dany wierzchołek II był już badany 11) lub nie (0)

<

t'IFO<int> kolejka(n); kolej ka.wstaw(i); int a;

while(!kolejka.pusta())

i

koićjka.obsłużjs);// bierzemy z kolejki pewien // wierzchołek 's'

V[s]=l;    II zaznaczamy '3' jako "zbadany"

for(int k=0;k<n;k++)

if(GIs]tk]!=0)    // istnieje przejście

if(V[k]==0)    II 'k' nie był jeszcze badany

1

Patrz §5.4