41 (523)

beęin [ procr^jr: dla ęrafu G, V -for v=V do

znak [vj : =nieodwiedzcr.y; (oznaczanie W5zyęckich s * >o ni eodwi ec z on e • er.d for; for vs V do

if z n a k (v ] =n i e od w i ed z cr. y then WGŁA3(v); end if; end for; end; tproęrŁir.)

zbiór

ierzchoików }

v; erze n c i k ó w n c n .7.7 * ,= - > 7

Analizując wykłady kolegi T.N wnioskuję, że działa to tak:

wszystkim wierzchołkom przypisujemy inicjując pracę wartość „nieodwiedzony**; wybieramy wierzchołek stanowi- i od razu nadajemy mu znak „odwiedzony'’; wybieramy dowolnego sąsiada 1 zmieniamy jego znak na „odwiedzony" również, gdy nie ma sąsiadów lub gdy wszyscy sąsiedzi zostali już odwiedzeni cofamy się i szukamy innej drogi w głąb. Przeszukanie w' głąb to inaczej odwiedzenie wszystkich wierzchołków' grafu w sposób jak „najszybszy'” i „najefektywniejszy”. Istnieje także nierekursywna metoda przeszukiwania grafu w głąb, ale nie zostanie tu omówiona za względu na jej małą atrakcijność (!).

Przykład:

Otrzymujemy w wyniku działania:

5 - 1,3, ’

Jako drzewo rozpinające w' głąb można podać takie krawędzie po wykonaniu tego algorytmu: (1, 2), (2, 3), (3,    (3, f). (Zaczynamy od wierzchołka 1).

Każdy wierzchołek grafu odwiedzany jest 1 - krotnie, a każda krawędź 2 - lar ot nie co daje w wyniku złożoność: 0(n: ej.

Nasz algorytm rozpoczyna przeszukiwanie od każdego wierzchołka w grafie, więc możliwa jest takie praca na grafie niespójnym! Jeśli pewne wierzchołki nie będą spójne z innymi to powstawać będą kolejne drzewu rozpinające dla kolejnych składowych spójności i w ten sposób będziemy mogli wszystkie je wyznaczyć.

Proste i jasne jak słoneczko!