45 (464)

if:

end vhil«;

«nd {procraz*

Podobno ogromną zaletą tego algorytmu jest to, że nie musi on przeglądać wszystkich gałęzi grafu, co ma znaczenie przy grafach bardzo rozbudowanych. Prowadzona jest cały czas kontrola lego czy nie zostały już sprawdzone wszystkie wierzchołki, jeśli tak program przerywa pracę. Więc, ( nie zaczyna się zdania

Priorytetowa lisia krawędzi z kosztami Q, to: (yj,v₇k (v>,v«), (v>,v7), (v>,v₇), (v₂,v₃), (v₄,v₇), (v₄,v₅), (v_Nv_:). (V|,v₆), (v₅,v₇), (v₃,v₆). (v₆,v₇). Wyjaśnienie działania algorytmu opane jest na poniższej tabelce ( jak podaje pro:". Z.CZ.):

| Krawędzi koleino z lisrv Q )	AiCCJA	Zbiorv’ w' VS
V|, V, I	-T	l(Vl.V7), (V2), (V,), fv4), (Vj), (Vf) !
| Vj I	W	Ifv,.v7y (v:y (v;.v.y (V5y (\\)
! V., v7 ) .	-	t(Vi,V:,v7), (v3,vj), (vjl£6)
1 Yju v7 i	-	l(v|,vi.v\,vj.v7).
V?. V? I		1
i v4. V, !	* .	1 i
v*. v5 |	-r	KV|,V:,V?,Vi,V5,V7), (vs) !
i V|.V;	-	1 ■ !
Vu v6 !		| (v.Mv:.V:,.vJtv<.Vf,v-)

Opis działania algorytmu jest zbyteczny pod warunkiem dokładnego przeczytania treści algorytmu i ‘ stosowania go wedle zamieszczonego przepisu. Powstaje wtedy taka tabelka, a drzewem rozpinającym o najmniejszym koszcie są krawędzie w lewej kolumnie tabeli. HOWGH !

Aby omówić złożoność tego algorytmu należy rozpatrzyć wszystkie rrzy fazy jego pracy.

-    pierwsza część 10 kolejka priorytetowa, która układana jest w czasie stałym zależnym od liczby elementów i złożoność jej zbudowania wynosi O(e);

-    druga to działanie pętli for, która pracuje ze złożonością 0(r)\

-    trzecią i najważniejszą częścią jest praca pętli while. Otóż wykona ona się e razy i za każdym obrotem pętli dokonane jest sprawdzenie if i ewentualnie łączenie zbiorów' co trwa pesymistycznie G(e log ej. ( log* k) 10 funkcja, która mówi ile razy należy logarytmować „k", aby otrzymać wynik <=0; np. dia k=l log*k=l, dla k=2 - 2, dla k=2⁶⁵⁵⁵⁶ -6).

Próbując dojść do kąsensusu probliema wynika, że złożoność jest rzędu 0(e log ej.