Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1º2ºPrzeszukiwσniegrσfuwszerz
21
odległośćto
0
ºNσstępnieprzetwσrzσnesąwierzchołki
v
,dlσktórychodległośćzostσłσ
jużwyznσczonσ,wkolejnościniemσlejącychodległościTdlσkσżdegonieodwiedzonego
sąsiσdσ
u
wierzchołkσ
v
przypisywσnesąwσrtości
t(u)=t(v)+1
,
5(u)=v
ºWwyniku
wykonσniσσlgorytmuBFSjestkonstruowσnylσsprzeszukiwσniσwszerz,wskłσdktó-
regowchodząwszystkiewierzchołkiosiągσlnezeźródłσwyszukiwσniσ,orσzkrσwędzie
konstruującenσjkrótsześcieżki(reprezentowσneprzezzmienne
5(v)
)ºZewzględunσto,
iżniewszystkiekrσwędziegrσfu
G
musząznσjdowσćsięwlesieprzeszukiwσniσBFS,
istniejemożliwośćklσsyfikσcjikrσwędzigrσfu
G
ºRozróżniσnesąwymienioneponiżejty-
pykrσwędzi,którychdefinicjσmσsenswprzypσdkurozpσtrywσniσkonkretnegolσsu
przeszukiwσniσ(definicjetesąużywσnenietylkowrσmσchprzeszukiwσniσwszerz)º
Definicja1050KrσwędźdrzewowσjesttokrIwędźgrIfU
G
?którInIleżgdowgznIczonego
lIsUprzeszUkiwIńo
Definicja1060KrσwędźniedrzewowσjesttokrIwędźgrIfU
G
?którInienIleżgdowg-
znIczonegolIsUprzeszUkiwIńo
Definicja1070KrσwędźpowrotnσjesttokrIwędźniedrzewowI?którIprowIdzizwierz-
chołkI
v
dojegoprzodkIwlesieprzeszUkiwIniIo
Definicja1080KrσwędźwprzódjesttokrIwędźniedrzewowI?którIprowIdzizwierz-
chołkI
v
dojegopotomkIwlesieprzeszUkiwIniIo
Definicja1090KrσwędźpoprzecznσjesttokrIwędźniedrzewowI?którIprowIdzizwierz-
chołkI
v
dowierzchołkIniebędącegoInijegopoprzednikiem?IninIstępnikiemwwgznI-
czongmlesieprzeszUkiwIńo
Wprzypσdkuprzeszukiwσniσwszerzgrσfównieskierowσnychniezσwierσjącychmul-
tikrσwędzikrσwędziewprzódorσzkrσwędziepowrotneniewystępują,nσtomiσstdlσ
grσfówskierowσnychniewystępująkrσwędziewprzódºWzσleżnościodrodzσjusto-
sowσnegoprzeszukiwσniσkrσwędzieposzczególnychtypówmogąmiećciekσwewłσsno-
ści,któresąwykorzystywσnewróżnegorodzσjuσlgorytmσchºNσjciekσwsząwłσsnością,
wprzypσdkuprzeszukiwσniσgrσfuwszerz,jestto,iżdlσkσżdejkrσwędzi
(ujv)∈E
zσ-
chodzi
d(u)=d(v)
lub
d(u)=d(v)±1
ºDziękitejwłσsnościσlgorytmBFSmożebyć
wykorzystywσnydowyznσczσniσnσjkrótszychścieżekmiędzyzσdσnąpσrąwierzchołkówº
AlgorytmBFSzostσłzreσlizowσnyjσkofunkcjσVoidGraph
<
V;E
>
..:fs(int),któ-
rσprzyjmujejedenpσrσmetrTnumerwierzchołkσbędącegoźródłemprzeszukiwσniσº
Implementσcjσwymσgσwzbogσceniσstrukturywierzchołkówodwiedodσtkowezmienne
TinttorσzintsºPowykonσniuσlgorytmunσgrσfiezmiennσinttjestrównσodległości
wierzchołkσodźródłσwyszukiwσniσ,σzmiennσintszσwierσnumerwierzchołkσ,zktó-
regoprowσdziznσlezionσnσjkrótszσścieżkσºZmienneintswyznσczσjątzwºlσsprze-
szukiwσniσgrσfuwszerzTprzykłσdtσkiegolσsuprzedstσwionyjestnσrysunku1º2º
ImplementσcjσfunkcjiVoidGraph
<
V;E
>
..:fs(int)znσjdujesięnσlistingu1º5º
