Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
1ºAlgorytmygrσfowe
1
3
(a)
2
4
1
3
(b)
2
4
(c)
Rysunek1010(a)Grifnieskierowiny1kriwędziełIczIcewierzchołki
1
i
2
sImultikriwędziimi?
i
(3,3)
topętliº(b)GrifskierowinyziwierijIcypętlę
(1,1)
orizmultikriwędzie
(1,2)
º(C)Grifindu-
kowinyprzezgrifzczęści(b)przezzbiórwierzchołków
{1,2,3}
1
3
2
będziemyczσsemużywσćpojęciσichstopniσºStopieńwejściowywierzchołkσtoliczbσ
krσwędzidoniegowchodzących,stopieńwyjściowyzσśtoliczbσkrσwędziwychodzących
zwierzchołkσº
Wwielumiejscσch,σwszczególnościprzyomσwiσniuzłożonościσlgorytmów,będzie-
myodwoływσćsiędoliczbywierzchołkóworσzkrσwędziwgrσfieºWsytuσcjσch,wktó-
rychzkontekstubędziejednoznσczniewynikσło,ojσkigrσfchodzi,liczbęwierzchołków
oznσczσćbędziemyprzez
n
,σliczbękrσwędziprzez
m
º
WtymrozdziσlejestopisσnychwieleσlgorytmówzwiązσnychzteoriągrσfówºPrzed-
stσwionesąmiędzyinnymimetodyprzeszukiwσniσgrσfów,topologicznesortowσniewierz-
chołków,sprσwdzσnie,czygrσfjestσcykliczny,wyznσczσniemσksymσlnegoprzepływu
orσzwieleinnychzσgσdnieńºZσnimjednσkprzejdziemydoσnσlizytychσlgorytmów,
musimynσjpierwpoznσćsposóbreprezentowσniσgrσfuwprogrσmσchº
1010Reprezentacjagrafu
Grσfbędziemyreprezentowσćprzyużyciuspσrσmetryzowσ-
nejstruktury(σngºtemplIte)Graph
<
V;E
>
,gdzieVjest
typemokreślσjącymdodσtkoweinformσcjeprzechowywσne
[2]T1º5º3,7
Literσturσ
[4]T22º1
[13]T2º1
[30]T3º3
wwierzchołkσch,σEjesttypemokreślσjącymdodσtkowe
informσcjeprzechowywσnewkrσwędziσchgrσfuºTσkwięc,
jeślichcemystworzyćgrσfmodelującysiećdrógwmieście,
towystσrczywzbogσcićstrukturęVoinformσcjezwiązσne
zeskrzyżowσniσmi,σstrukturęETzulicσmiº
ImplementσcjσgrσfuudostępniσdwσoperσtoryGraph
<
V;E
>
..EdgeD(int9int9E)
orσzGraph
<
V;E
>
..EdgeU(int9int9E),służąceodpowiedniodododσwσniσdogrσ-
fukrσwędziskierowσnychorσznieskierowσnych(σngºdirectedTskierowσne;Undirected
Tnieskierowσne)ºPierwszyidrugipσrσmetrtychfunkcjiokreślσjąnumerywierzchoł-
kówpołączonychdodσwσnąkrσwędzią,σostσtnipσrσmetrdefiniujedodσtkoweinfor-
mσcjezwiązσneztąkrσwędziąºDlσwiększościσlgorytmówkorzystσjącychzestruktury
Graph
<
V;E
>
tedwσoperσtorysąwzupełnościwystσrczσjące,σlewrσziepotrzeby
możnσwprostysposóbwzbogσcićimplementσcjęonoweoperσcjeTchociσżbyfunkcję
usuwσjącąkrσwędziezgrσfuº
Listing1º1zσwierσimplementσcjęstrukturyGraph
<
V;E
>
wrσzzkomentσrzσmiwy-
jσśniσjącymiprzyjęterozwiązσniσºImplementσcjσtσwykorzystujebibliotekęSTL(do-
kłσdniej,kontenervectordoreprezentowσniσlistywierzchołkówikrσwędzi)º
