Metodedeexplorareagrafurilor.Explorarea (sau traversarea ) unui graf este o metod sistematic de parcurgere, prin examinareamuchiilorivrfurilor.OtraversareeficientarelocntimpliniarO(n+m).

Traversareanadncimeaunuigraf(DFSDepthFirstSearch).

Incazulgrafurilorneorientate,traversareanadncimeesteometodeficientpentru: gsireauneicintredouvrfuri adeterminadacungrafesteconex determinareaarboreluideacoperireaunuigrafconex

PrintraversareaDFSaunuigrafneorientatseobineunarboredeacoperirenadncime.

Inacestscop: sepornetedintrunvrfs(vrfdestart).Iniialvrfulcurentuvafivrfuldestart.Fie(u,v)o

muchieincidentnvrfulcurentu.Suntposibile2situaii: vrfulvnuafostncexplorat(vizitat),cazncare:

semarcheazvrfulcavizitat secontinuexplorareadinv

vrful v afostdejavizitat,situaiencareserevinen uisencearcvizitareaunuialtvrfadiacentluiu

dacsauvizitattoatevrfurileadiacenteluiu,sefaceunpasnapoi,alegndaltvrfcurentu,cumuchiineexplorate,Procesulsencheiecndnentoarcemns.

Muchiaexploratdinu,careconducelaunvrfnedescoperitesteomuchiedearbore.Omuchiedinu,careconducelaunvrfdejavizitat,esteomuchiederevenire.Eaindicprezenaunuiciclu.

FieotraversareDFSntrungrafneorientatG,porninddinvrfuldestartu: traversareaviziteaztoatevrfurilecomponenteiconexealuis muchiiledearboreformeazunarboredeacoperireacomponenteiconexealuis.

In traversare, funcia DFS este apelat o singur dat pentru fiecare vrf, a.. fiecare muchie esteexaminat de 2 ori, cte o dat pentru fiecare extremitate. Complexitatea algoritmului va fi aadarO(n+m).

Urmtoriialgoritmisebazeazpetraversarenadncime(DFS)iauaceeaicomplexitate:1) testconexitategraf2) determinarearboredeacoperirepentrugrafconex3) determinarecomponenteconexealegrafului4) determinareauneicintredouvrfuri5) determinareaunuiciclu(saudeterminareainexisteneiciclurilor).

Traversareanadncimeaunuigrafneorientatclasificmuchiilegrafuluin: muchiidearbore muchiiderevenire

algoritmDFS(u)forfiecaremuchieeincidentnuv=cealaltaextremitatealuie;ifvnevizitate>tip=arbore;DFS(v);elsee>tip=revenire;

ArboreledeacoperirenadncimeestepstratprinsubgrafulpredecesorGp=(V,Ep)ncare:

1

Ep={(pred(v),v):vVpred(v) 0}SeobservcEppstreazmuchiiledearbore.

voidDFSV(GrafG,Varfu){Varfv;G_SetCol(G,u,gri);for(v=primV(G);!dultV(G);v=avansV(G,v))if(G_IsV(G,v)&&G_IsA(G,u,v)&&G_GetCol(G,v)==alb){G_SetPred(G,v,u);DFSV(G,v);}}voidDFS(GrafG){Varfu;for(u=primV(G);!dultV(G);u=avansV(G,u))if(G_IsV(G,u)){G_SetCol(G,u,alb);G_SetPred(G,u,0);};for(u=primV(G);!dultV(G);u=avansV(G,u))if(G_IsV(G,u)&&V_GetCol(u)==alb)DFSV(G,u);}

Spredeosebiredegrafurileneorientate,lacarencursultraversriiunvrfpoatefivizitatsaunevizitat,pentrugrafuriorientate,sedisting3stri,identificateprinculori:0 = albpentruvrfnevizitat1 = gripentruvrfvizitat,acruilistdesuccesorinuafostnntregimeexplorat2 = negrupentruvrfvizitat,culistdesuccesoriexploratPentrufiecarevrfusemarcheazdoumomente:start[u]=momentuldescopeririivrfuluistop[u]=momentulncaresaexploratlistadesuccesoriaivrfuluiu

Intrungraforientat,arceleaccesibiledinsseclasificn: arcedearborecareconducladescoperireadevrfurinoi arcederevenirecareleagunvrfcuunstrmonarboreleDFS arcedenaintarecareleagunvrfcuundescendentnarboreleDFS arce de traversare care leag vrfuri din arbori DFSdiferii (nu se ncadreaz ncategoriile

precedente).

intstart[2*M],stop[2*M];intt;voidDFS(GrafG){Varfu;for(u=primV(G);!dultimV(G);u=avansV(G,u))if(G_IsV(G,u)){G_SetCol(G,u,alb);G_SetPred(G,u,0);};t=0;for(u=primV(G);!dultimV(G);u=avansV(G,u))if(G_IsV(G,u)&&G_GetCol(G,u)==alb)DFSV(G,u);}

2

void DFSV(Graf G, Varfu){Varfv;G_SetCol(G,u,gri);start[u]=++t;for(v=primV(G);!dultimV(G);v=avansV(G,v))if(G_IsV(G,v)&&G_IsA(G,u,v)&&G_GetCol(G,v)==alb){G_SetPred(G,v,u);DFSV(G,v);};G_SetCol(G,u,negru);stop[u]=++t;}

OfuncieDFSnerecursivfoloseteostiv:

DFS(G,s){punenoduldestartinstiv;cttimp(stivnevid){scoatedinstivnx;marcarex;punenstivsuccesoriinevizitaiailuix;}}

voidDFSV(GrafG,Varfu){StivaS=S_New();Push(S,u);Varfx,v;while(!S_Empty(S)){x=*(Varf*)Pop(S);if(G_GetCol(G,x)==alb){G_SetCol(G,x,gri);for(v=primV(G);!dultimV(G);v=avansV(G,v))if(G_IsV(G,v)&&G_IsA(G,x,v)&&G_GetCol(G,v)==alb){Push(S,v);G_SetPred(G,v,u);}}}}

TraversareaDFSpoatefolosilaclasificareaarcelor.Astfeldac: colorat[v]=alb(u,v)arcdearbore colorat[v]=gri(u,v)arcderevenire colorat[v]=negru start[u]start[v](u,v)arcdetraversare

3

a b e f

c d

1/12 2/11 8/9 5/6

3/10 4/7virf Lista

succesoria b cb cc d ed fe b ff

virf

pred

colorat start stop

a 0 0 1 2 1 12b 0 a 0 1 2 2 11c 0 b 0 1 2 3 10d 0 c 0 1 2 4 7e 0 c 0 1 2 8 9f 0 d 0 1 2 5 6

Traversareanlime(BFSBreadthFirstSearch).

PrintraversareanlimeaunuigrafG = (V, E)secreazunarboredeparcurgerenlime:Gp=(Vp,Ep)Vp={vV:pred[v] 0}{s}Ep={(pred[v],v)E:vVp{s}}

Folositpentruafiareaciidelavrfuldestartslaunvrfv:

voidafiscale(GrafG,Varfs,Varfv){if(v==s)printf(%s\n,V_GetEt(v));elseif(G_GetPred(G,v)==0)printf(nuexistadrum\n);else{afiscale(G,s,G_GetPred(G,v));printf(%s\n,G_GetEt(G,v));}}

Printraversareanlime,porninddinvrfulsurss: secalculeazdistana(nnumrdemuchii)delasurslafiecarevrf

4

pentruoricevrfv,accesibildinsursas,caleanarborecorespundeceluimaiscurtdrumdelaslavvoid BFS(Graf G, Varf s){ Varf u,v; Queue Q=Q_New();for(u=primV(G);!dultimV(G);u=avansV(G,u)){if(G_IsV(G,u)){G_SetCol(G,u,alb);G_SetDist(G,u,INF);G_SetPred(G,u,NULL);}}G_SetCol(G,s,gri);G_SetDist(s,0);Enq(Q,s);while(!Q_Empty(Q)){u=Front(Q);for(v=primVAd(G,u);!dultVAd(G,u);v=avansVAd(G,u,v)if(G_GetCol(G,v)==alb){G_SetCol(G,v,gri);G_SetDist(G,v,G_GetDist(G,u)+1);G_SetPred(G,v,u);Enq(Q,v);}Deq(Q);G_SetCol(G,u,negru);}}

R

V

S

W

T

X

U

Y

1 0 2

2 1 2

3

3

virf pred colorat ds 0 012 0r 0s 012 1t 0w 012 2u 0t 012 3v 0r 012 2w 0s 012 1x 0w 012 2y 0x 012 3

5

EvoluiacoziipeparcursulexecuieialgoritmuluiBFSeste:

QQQQQQQQQQQQQQQQ.ssrsrwrwrwvwvwvtwvtxvtxtxtxuxuxuyuyy

Printraversareanlimeaunuigrafneorientataparmuchiidearboreimuchiidetraversare.Latraversareanlimeaunuigraforientatapar:arcedearbore,arcedetraversareiarcederevenire.

Arboreledeparcurgerenlimeeste:

S

A

R

V

W

T X

U YT

T

A A

AAA

A

Sortaretopologic.

Intrungraforientatprezenaunuiarc(u, v)poatefiprivitcaorelaiedepreceden:u precede v. Reciproc, mai multe elemente ntre care exist relaii de preceden pot fireprezentateprintrungraforientat.Dacnuexistcicluri,esteposibilgsireauneirelaiideordinepeansamblultuturorvrfurilorgrafului.Osortaretopologicaunuigraforientataciclicesteoordonareliniardevrfurincareu precedev,dacexistarcul(u,v).Unalgoritmdesortaretopologicarconsideramaintivrfurilecarenusuntprecedate(condiionate)dealtevrfuri,adicvrfurilesurs(cugradinteriornul),dupcareurmeazvrfurilecaresuccedpeceledinti.a.m.d.

dogasesteunvrfvcuindeg[v]=0punevncoadtergevrfulviarceleincidentenvrfwhilemaisuntvrfuri)

Sortarea topologic sepoaterealizaprintrotraversare nadncime(DFS).Unvrf carenumaiaresuccesori(coloratnegru)aregraddeieire0,deciaparendreaptairuluidevrfurisortatetopologic;elvafipusnstiv,a..nvrfulstiveivoraparevrfurilecugraddeintrare0.

6

void topsort(GrafG,Varfu){StivaS=S_New();Varfv;G_SetCol(G,u,gri);for(v=primV(G);!dultimV(G);v=avansV(G,v))if(G_IsV(G,v)&&G_IsA(G,u,v)&&G_GetCol(G,v)==alb)topsort(G,v);Push(S,u);}

Pentrugrafuldemaijos:

a

b c

d f

e h

g

Pdureadeacoperirenadncimeeste:

a b dc

e

f

g h

Elementelesuntpusenstivnordinea:dcbaefhg , decisortareatopologiceste:ghfeabcdSeconstatcexistmaimultevariantedesortaretopologic,deoarecevrfurileindependente,avndlaunmomentdatgraduldeintrare0potficonsideratenoriceordine.

Determinareacomponentelortareconexe.

OcomponenttareconexaunuigraforientatG=(V,E)esteunsetmaximaldevrfuriUVa..pentruu,vUavemuvivu (vrfurileuivsuntaccesibileunuldincellalt).

Seformeazgrafultranspus,inversnddireciaarcelor.

GT=(V,ET)ET={(u,v):(v,u)E}

GrafurileGiGTauaceleaicomponentetareconexe.

Algoritmulpentrucalcululcomponentelortareconexepresupunedoutraversrinadncime:nprimatraversareagrafuluiGsecalculeaztimpiiterminriistop[u]pentrufiecarevrfu.Adouatraversare

7

sefaceasupragrafuluitranspusGTnordineavrfurilordictatdevectorulstop[].Fiecarearboredinpdureadeacoperirenadncimeaceleideadouaparcurgerireprezintocomponenttareconex.

CTC(G)DFS(G)CalculGT

DFS(GT)nordineadictatadestop[]

a b c d

e f g h

1/16 2/15 3/12 4/7

13/14 9/10 8/11 5/6

abbcefcdgdcheaffggfhh

varf pred color start stop1a 0 0 1 2 1 16b 0 a 0 1 2 2 15c 0 b 0 1 2 3 12d 0 c 0 1 2 4 7e 0 b 0 1 2 13 14f 0 g 0 1 2 9 10g 0 c 0 1 2 8 11h 0 d 0 1 2 5 6

Grafultranspuseste:

a b c d

e f g h

aebacbd

dcebfbeggcfhdg

8

ab

c e

fh

gd

A

A A

T

I

R

A

A

A

R

T

R

varf stop1 pred color start stop ha 16 0 0 1 2 1 6b 15 0 e 0 1 2 3 4e 14 0 a 0 1 2 2 5c 12 0 0 1 2 7 10g 11 0 0 1 2 11 14f 10 0 0 1 2 12 13d 7 0 0 1 2 8 9h 6 0 0 1 2 15 16

a

e

b

c

d

g

f

h

abe cd

fg h

9

Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q.