Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
18
1ºAlgorytmygrσfowe
zostσćumieszczonσwobrębiestrukturyGraph
<
V;E
>
ºFσktutegowdσlszejczęściksiąż-
kiniebędziemywięcejprzywoływσćTzdσjemysięnσdobrąpσmięćczytelnikσº
Jσkozσdσnienrozgrzewkoweπnσpiszemyprostąfunkcjęwypisującąstrukturęgrσfu
nσstσndσrdowewyjścieºNσpoczątkukσżdegowierszσopisupowinienznσleźćsięnumer
kolejnegowierzchołkσ(numeryzσczynσjąsięod
0
),σnσstępnielistσwierzchołków,zktó-
rymitenwierzchołekjestpołączonykrσwędziąºPrzykłσdowσimplementσcjσtejfunkcji
przedstσwionσjestnσlistingu1º2º
Listing1020ImplementicjifunkcjiVoidGraph
<
V>E
>
..Writę()
º
º
1VoidWritę(){
//Dlawszystkichwięrzchołkówwgrafię9zaczynającod0ººº
2
REP(Ü>SlZE(g)){
//Wypisznumęrwięrzchołka
3
cout
<<
Ü
<<
fl.fl;
//DlakażdęjkrawędziwychodzącęjzprzętwarzanęgowięrzchołkaonumęrzęÜ
//wypisznumęrwięrzchołka9doktóręgoonaprowadzi
4
FOREACH(it>g[Ü])cout
<<
flfl
<<
it-
>
V;
5
6
7}
}
cout
<<
ęndl;
Zσłóżmy,żewplikuznσjdujesięopisgrσfuskierowσnegownσstępującymformσciel
wpierwszymwierszusązσpisσnedwieliczbynσturσlne
n
i
m
,oznσczσjąceodpowiednio
liczbęwierzchołkóworσzkrσwędziwgrσfie(wierzchołkinumerowσnesąod
0
do
n−1
)º
Wkolejnych
m
wierszσchsąumieszczonepodwieliczbynσturσlne
b
i
e
,oznσczσjące,
żezwierzchołkσonumerze
b
prowσdzikrσwędźskierowσnσdowierzchołkσonumerze
e
º
Chcemynσpisσćprogrσm,któryprzekonwertujeopistegogrσfunσformσt,jσkijestge-
nerowσnyprzezfunkcjęVoidGraph
<
V;E
>
..Write()º
Dlσnσstępującegoopisuwejściowegol
58
01
34
41
40
12
24
32
43
Progrσmwygenerujenσstępującywynikl
0.1
1.2
2.4
3.42
4.103
RozwiązσniejestprosteTwystσrczywykorzystσćstrukturęGraph
<
V;E
>
,nσpod-
stσwieopisuzplikuskonstruowσćodpowiednigrσf,σnσstępniewypisσćjegostrukturę
przyużyciufunkcjiVoidGraph
<
V;E
>
..Write()ºGłównσczęśćprogrσmureσlizującego
tozσdσnieprzedstσwionσjestnσlistingu1º3ºPominiętewnimzostσłystσndσrdowenσ-
główkipochodzącezbiblioteczkiºWłσśniewtensposóbwdσlszejczęściksiążkibędą
prezentowσneprzykłσdoweprogrσmyºPoniewσżomówionytuprzykłσdjestpierwszym
kompletnymprogrσmem,jσkidotejporyudσłonσmsięstworzyć,zσtemnσlistingu1º4
