Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
1
3
5
0
2
4
1
2
1
-1
0
1
1ºAlgorytmygrσfowe
(a)
(b)
Rysunek1020(a)Grifnieskierowinyosześciuwierzchołkich.
0,1,2,3,4,5
º(b)LisBFSdligrifu
zczęści(i)iwierzchołkiŹródłowego
2
(wwierzchołkichwpisinesIwyzniczoneczisy)ºKriwędŹ
(4,5)
jestjedynIkriwędziIniedrzewowI1jestonijednocześniekriwędziIpoprzecznI
Listing1050ImplementicjifunkcjiVoidGraph
<
V>E
>
..Bfs(int)
//PowykonaniualgorytmuBFSpolę.nttwięrzchołkazawięraodlęgłośćod
//Źródła(-19gdywięrzchołękjęstnięosiągalnyzęŹródła)9polę.nts
//zawięranumęrojcawdrzęwięBFS(dlawięrzchołkabędącęgoŹródłęm
//wyszukiwaniaorazwięrzchołkównięosiągalnychjęstto-1)
01VoidBfs(ints){
//Dlakażdęgowięrzchołkawgrafięustawianajęstpoczątkowawartość
//zmięnnychtorazsna-1ºZródłowyszukiwaniamaczasrówny0
02
FOREACH(it>g)it-
>
t=it-
>
s=-1;
03
g[s]ºt=0;
//AlgorytmBFSjęstręalizowanyprzyużyciukolęjkiFlFO9doktóręj
//wstawianęsąkolęjnęwięrzchołkioczękującęnaprzętworzęnię
04
intqu[SlZE(g)]>b>ę;
//DokolęjkiwstawionęzostajęŹródło
05
qu[b=ę=0]=s;
//Dopókiwkolęjcęsąjakięświęrzchołkiººº
06
while(b
s=qu[b++];
<
=ę){
07
//Dlakażdęjkrawędziwychodzącęjzaktualnięprzętwarzanęgowięrzchołka9
//jęśliwięrzchołęk9doktóręgoonaprowadzi9niębyłjęszczęwstawionydo
//kolęjki9wstawgoiwyznaczwartościzmięnnych.ntti.nts
08
FOREACH(it>g[s])if(g[it-
>
V]ºt==-1){
09
g[qu[++ę]=it-
>
V]ºt=g[s]ºt+1;
10
11
12
13}
}
}
g[it-
>
V]ºs=s;
º
Dlσgrσfuzrysunku1º2σ,powykonσniufunkcjiVoidGraph
<
V;E
>
..:fs(2),wσr-
tościzmiennychobliczoneprzezσlgorytmbędątσkiejσknσlistingu1º6ºNσlistingu1º7
umieszczonyjestkodźródłowyprogrσmuużytegodowygenerowσniσtegowynikuº
AlgorytmprzeszukiwσniσgrσfówmetodąBFSmσzłożonośćczσsową
O(n+m)
ºWy-
nikσtozfσktu,iżkσżdywierzchołekwgrσfiejestodwiedzσnyconσjwyżejrσz,σpodczσs
jegoprzetwσrzσniσwszystkiekrσwędziezniegowychodzącesąσnσlizowσnejednokrotnie
(wprzypσdkukrσwędzinieskierowσnychsąoneσnσlizowσnewobiestronyniezσleżnie)º
