42 (482)

Proponuję namalować coś niespójnego (Jarek ..'.???) i spróbować to coś przeszukać. Działa - a wiadomo, że najlepiej uczyć się na własnych przykładach.

55. Przedstawić przeszukiwanie grafu wszerz. Podać zastosowanie tego przeszukiwanie do problemu znajdowania najkrótszej ścieżki w grafie (długość ścieżki liczona ilością włączonych do drogi krawędzi).

Podajm)' najsampterw algorytm, : ang lisia fbreodlh first searchj:

procedura WSZZR2 (v) ;    (przeszukiwani® wszerz w z wierzchołka v" }

%hłt K; (kolejka wierzchołków - FITO } begin

znak(v]:=odwieĆ2onv;

wsęaw_óo_kolej ki (v, K) ; (funkcja wstawia wierzchołek „v" co kolejki „K"} vhxle not pusta kolejka(K) do x:-Pierwszy (k) ;

usuń pierwszy z ko-łe j..ki (K); [usuwa pierwszy wierzchołek z kolejki „X"J for (y e(lista incydencji{x}]) do

if znak[yj = nieodwieazony then zr.a k ( v ] : = oawi edzor. y ;

wszaw^dc_kclejki (y, K) ;    (wstawia wierzchołek „y" ćz

kolejki „K") end if; end for; end whiłe; end (procedure];

szu k i wa r.i e era z u <«:**(>, —} wszerz;; y eV) do

begin (p: for

i a jako

wiar : cno z o w w

end

for

nieocwiedzone} for ;

(yeV) do

end

end (próg

o

No. Dziad to tuk.

if znak ( v] =:iieocwiedzony then WSZ—RZ(v); end if; for;

■a_tł} ;

Jeśli startujemy z wierzchołka (1) to na początku drzewo przeszukiwana wszerz zawiera wszystkie krawędzie z wierzchołka l i do dalszej rekursii wybierany jest pierwszy wierzchołek z kolejki (dla (1) w kolejce stoją za (1) - (2) i (5), czyli wybieramy (2)). Zakładam, ze lista incydencji z danego wierzchołka poszeregowana jest rosnąco .i tak tez wierzchołki są wybierane przez algorytm. Po przeanalizowaniu algorvtmu drzewo przeszukiwania wszerz ma postać-(kolejno z wierzchołka (1) - Lak jak powstawały krawędzie): (1, 2), (1, 5), (2, 3), (2, 6), (2, 7), (5, 4).

Działa jak cholera !!!