Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
26
1ºAlgorytmygrσfowe
d
i
f
reprezentująodpowiednioczσsywejściσiwyjściσzwierzchołkσ,σ
5
tonumer
wierzchołkσ-ojcσwwyznσczonymlesieDFSºWσlgorytmiezσkłσdσsię,żekσżdσwyko-
nywσnσoperσcjσ(wejścieiwyjściezwierzchołkσ)zσjmujejednostkęczσsuºCzσswejściσ
dowierzchołkσ
v
jestrozumiσnyjσkomoment,wktórymrozpoczętoprzetwσrzσnietego
wierzchołkσ(przeszukiwσnieDFSporσzpierwszyodwiedziłotenwierzchołek),σczσs
wyjściσzwierzchołkσ
v
,toczσs,wktórymprzetwσrzσniewierzchołkσ
v
zostσłozσkoń-
czoneºZewzględunσrekurencyjneodwiedzσniewszystkichsąsiσdówwierzchołkσ
v
przed
zσkończeniemjegoprzetwσrzσniσczσsywejściσorσzwyjściσreprezentująpoprσwnąstruk-
turęnσwiσsową,wktórejwejściedowierzchołkσjestreprezentowσneprzeznσwiσsotwie-
rσjący,nσtomiσstwyjścieprzeznσwiσszσmykσjącyºNσrysunku1º3d,eprzedstσwionσ
jestprzykłσdowσkolejnośćprzetwσrzσniσwierzchołkówgrσfuº
CzσsywyznσczσneprzezσlgorytmDFSmσjąwielezσstosowσńTsłużąmiędzyinnymi
doznσjdowσniσmostów,punktówσrtykulσcjibądźsilniespójnychskłσdowychwgrσfσchº
Zmiennσ
5
dlσwierzchołkσ
v
(podobniejσkwσlgorytmieBFS)reprezentujenumerwierz-
chołkσ,zktóregowierzchołek
v
zostσłodwiedzonyTwszystkiewσrtości
5
wyznσczσją
lσsprzeszukiwσńwgłąb(przykłσdytσkichlσsówsąpokσzσnenσrysunkσch1º3borσz
1º3c)º
ImplementσcjσσlgorytmuDFS,przedstσwionσnσlistingu1º8,jestzreσlizowσnσprzez
funkcjęVoidGraph
<
V;E
>
..DfsR(int),przyjmującąjσkopσrσmetrnumerwierzchołkσ,
zktóregonσleżyrozpocząćprzeszukiwσnieºGdypσrσmetrtenniezostσłpodσny,wyko-
nywσnejestprzeszukiwσniezewszystkich,jeszczenieodwiedzonychwierzchołkówgrσfu,
wkolejnościrosnącychnumerów(przykłσdtσkiejsytuσcjiwidσćnσrysunku1º3c)º
0
2
4
6
(a)
3
1
-1/-1
-1/-1
0/3
1/2
3
5/8
0/9
4/13
7/12
5
6/7
5/6
2/3
9/10
1/4
8/11
(b)
0
2
1
4
3
(e)
6
5
(c)
6
5
2
4
(d)
Rysunek1030(a)Przykłidowygrifnieskierowinyosiedmiuwierzchołkichº(b)DrzewoDFSdli
Źródłiwyszukiwiniiwwierzchołku
3
(wewnItrzwierzchołkówwpisinesIodpowiednioczisywejścii
orizwyjścii)º(C)DrzewoDFSdliprzeszukiwiniiciłegogrifuwkolejnościrosnIcychnumerówwierz-
chołków(odpowiednikwywołiniifunkcjiVoiàGraph
<
V
¸
E
>
00DfS())º(à)Kolejnośćprzeszukiwinii
wierzchołkówdlidrzewiDFSzczęści(b)º(e)KolejnośćprzeszukiwiniiwierzchołkówdlidrzewiDFS
zczęści(c)
