Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1º3ºPrzeszukiwσniegrσfuwgłąb
27
Listing1080RekurencyjniimplementicjiprzeszukiwiniiDFS)zreilizowinijikofunkcjiVoid
Graph
<
V>E
>
..DfsR(int)
º
//Wpolu.ntdkażdęgowięrzchołkaalgorytmumięszczaczaswęjścia9wpolu
//.ntf-czaswyjścia9natomiastwpolu.nts-numęrojcawlęsięDFS
//(wartościtędlawięrzchołkównięodwiędzonychsąrównę-1)
//Zmięnnatjęstużywanadopamiętaniaaktualnęgoczasuprzętwarzania
01intt;
//FunkcjarękuręncyjnaprzęszukującapoddrzęwowięrzchołkaVmętodąDFS
02VoidDfsV(intV){
//Ustawczaswęjściadowięrzchołka
03
g[V]ºd=++t;
//DlakażdęjkrawędziwychodzącęjzwięrzchołkaV9jęśliwięrzchołęk9do
//któręgoprowadzikrawędŹ9niębyłjęszczęodwiędzony9togoodwiędŹ
04
FOREACH(it>g[V])if(g[it-
>
V]ºs==-1){
05
}
g[it-
DfsV(it-
>
V]ºs=V;
>
V);
06
07
//Ustawczaswyjściazwięrzchołka
08
g[V]ºf=++t;
09}
10VoidDfsR(intę=-1){
11
t=-1;
12
intb=0;
//Dlawięrzchołkówzprzędziału[bººę]zostanięwywołanafunkcja
//Vo.dDfsV(.nt)ºJęślidofunkcjiVo.dDfsR(.nt)nięprzękazano
//paramętru9toprzędziałęmtymjęst[0ººSlZE(g)-1](wszystkię
//więrzchołkiwgrafię)9wprzęciwnymrazię[ęººę](tylkojędęn
//więrzchołęk)
13
ę==-1?ę=SlZE(g)-1.b=ę;
14
REP(Ü>SlZE(g))g[Ü]ºd=g[Ü]ºf=g[Ü]ºs=-1;
//WykonajalgorytmDFSdlawszystkichwięrzchołkówzprzędziału[bººę]
15
FOR(Ü>b>ę)if(g[Ü]ºs==-1)DfsV(Ü);
16}
ImplementσcjσprzeszukiwσniσgrσfumetodąDFS,reσlizowσnσprzezfunkcjęVoid
Graph
<
V;E
>
..DfsR(int),jestrekurencyjnσºPodejścietσkiejeststosunkowoproste
wreσlizσcji(niejestwymσgσneimplementowσniewłσsnegostosuσktuσlnieprzetwσrzσ-
nychwierzchołków),jednσkpodczσsoperowσniσnσdużychgrσfσchpojσwiσsięryzyko
przepełnieniσstosuprogrσmu,σcozσtymidzieTdoprowσdzeniedobłęduwykonσniσº
Wprzypσdkuprzeszukiwσniσdużychgrσfównσleżysięupewnić,żewsystemieoperσ-
cyjnym,wktórymbędziewykonywσnyprogrσm,niemσdodσtkowegoogrσniczeniσnσ
stoslubjestononσtyleduże,żeniezσgrσżσdziσłσniuprogrσmuºGdynieistniejemożli-
wośćskorzystσniσzrekurencyjnejimplementσcjiσlgorytmu,możnσużyćimplementσcji
iterσcyjnej,reσlizowσnejprzezfunkcjęVoidGraph
<
V;E
>
..Dfs(int)ºKodźródłowytej
funkcjiprzedstσwionyjestnσlistingu1º9º
