ALG 8

258

Rozdział 10. Elementy algorytmiki grafa

1

Rys. 10- 10.

Przeszukiwanie grafu „ w głąb

Listu wierzchołków przyległych:

0    - I. 3. 4

1    - 0. 2. 4 2-1.6

3 - 0. 4. 6 4-0. I. 3. 5 5 - 4

6 - 2. 3

Usta wierzchołków przyległych do danego wierzchołka jest dla ułatwienia wypisana obok grafu'.

Algorytm przeszukiwania „w głąb” zapisuje się dość prosto w C++:

deplltjlcpp

int i,j, G(n][n], V[n];

// G - graf nxn

// V - przechowuje informacje, czy dany wierzchołek !/ był już badany (1) lub nie (0) void szuka;(int G[n|[n], int V(n])

I

int i;

for(i=0;i<n;i n}

V[i]=0; // wierzchołek nie był jeszcze badany for(i=0;i<n;i++) if (V ( i] ==0) zwiedzaj(G,V,i);

I void zwiedzaj(int Gin¹ fnl, int Vfn], int i)

t

V[i]=l;    // zaznaczamy wierzchołek jako "zbadany"

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

if (G[i] [k] ! =0)    // ist.nieie przejście

if(V[k]==0) zwiedzaj(G,V,k);

1

Jak łatwo zauważyć, składa on się z dwóch procedur: szukaj, która inicjuje sam proces przeszukiwania i zwiedzaj, która tak ukierunkowuje proces przeszukiwania, aby postępował on naprawdę „w głąb”. Procedura zwiedzaj przeszukuje listę wierzchołków przylegających do wierzchołka ‘i’, zatem jej właściwa treść (w pseudokodzie) przedstawia się w ten sposób:

’ Kolejność elementów w lej liście jest związana z użyciem reprezentacji tablicowej, w której indeks tablicy (czyli numer węzła) z góty narzuca pewien porządek wśród węzłów.