Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1º1ºReprezentσcjσgrσfu
Listing1010ImplementicjistrukturyGraph
<
V>E
>
17
º
01template
<
classV>classE
>
structGraph{
//Typkrawędzi(Ed)dziędziczypotypięzawięrającymdodatkowęinformację
//związanęzkrawędzią(E)ºZawięraonrówniężpolęV9okręślającęnumęr
//więrzchołka9doktóręgoprowadzikrawędŹºZaimplęmęntowanykonstruktor
//pozwalanaskrócęnięzapisuwięlufunkcjikorzystającychzęstrukturygrafu
02
structEd.E{
03
intV;
04
Ed(Ep>intw).E(p)>V(w){}
05
};
//Typwięrzchołka(Vę)dziędziczypotypięzawięrającymdodatkowę
//informacjęznimzwiązanę(V)orazpowęktorzękrawędziºTodrugię
//dziędziczęnięmożęwydawaćsięnapięrwszyrzutokastosunkowodziwnę9
//lęczjęstonoprzydatnę-umożliwiałatwęitęrowaniępowszystkich
//krawędziachwychodzącychzwięrzchołkaV.FOREACH(it9g[V])
06
structVę.V>Vęctor
<
Ed
>
{};
//Węktorwięrzchołkówwgrafię
07
Vęctor
<
Vę
>
g;
//Konstruktorgrafu-przyjmujęjakoparamętrliczbęwięrzchołków
08
Graph(intn=0).g(n){}
//FunkcjadodającadografunowąkrawędŹskięrowanązwięrzchołkabdoę9
//zawięrającądodatkowęinformacjęokręślonęprzęzzmięnnąd
09
VoidEdgęD(intb>intę>Ed=E()){
10
g[b]ºPB(Ed(d>ę));
11
}
//FunkcjadodającadografunowąkrawędŹnięskięrowaną9łączącąwięrzchołki
//bięorazzawięrającądodatkowęinformacjęokręślonęprzęzzmięnnądº
//KrawędŹnięskięrowanajęstrępręzęntowanaprzęzdwiękrawędzię
//skięrowanę-jędnąprowadzącązwięrzchołkabdowięrzchołkaęoraz
//drugąprowadzącązwięrzchołkaędowięrzchołkabºStrukturaEwgrafach
//nięskięrowanychmusidodatkowozawięraćęlęmęnt.ntręVºDladanęj
//krawędziskięrowanęj(b9ę)polętoprzęchowujępozycjękrawędzi(ę9b)
//naliścięincydęncjiwięrzchołkaęºDziękitęmudladowolnęjkrawędzi
//wgrafięmożnawczasięstałymznalęŹćkrawędŹoprzęciwnymzwrocię
12
VoidEdgęU(intb>intę>Ed=E()){
13
Edęg(d>ę);
14
ęgºręV=SlZE(g[ę])+(b==ę);
15
g[b]ºPB(ęg);
16
ęgºręV=SlZE(g[ęgºV=b])-1;
17
g[ę]ºPB(ęg);
18
}
19};
Wkolejnychpodrozdziσłσchdotyczącychteoriigrσfówzostσnąprzedstσwioneim-
plementσcjeróżnychσlgorytmówwykorzystującychstrukturęGraph
<
V;E
>
ºWszystkie
funkcjereσlizująceteσlgorytmysąmetodσmigrσfu,σcozσtymidzie,ichtreśćmusi
