Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Parcurgerea grafurilor in adancime

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Algoritmi speciali - Sortarea unui vector
Coada - Utilitatea unei cozi - Inserarea unui element in coada
ALGORITMI DE CALCUL SI STRUCTURI DE DATE
SYSAMO-SISTEM EXPERT PENTRU AMORTIZAREA IMOBILIZARILOR CORPORALE
AUTOMATE FINITE IMPLEMENTATE IN VERILOG
REPREZENTAREA SI PRELUCRAREA INFORMATIEI IN CALCULATOARELE NUMERICE
Probleme cu algoritmi si cheme logice
ALGORITMUL HOOKE-JEEVES
METODE DE SORTARE
Clusterizare - Algoritmul K-means

Parcurgerea grafurilor in adancime

Fie = <VM> un graf orientat sau neorientat, ale carui varfuri dorim sa le consultam. Presupunem ca avem posibilitatea sa marcam varfurile deja vizitate in tabloul global marca. Initial, nici un varf nu este marcat.



Pentru a efectua o parcurgere in adancime, alegem un varf oarecare, v I V, ca punct de plecare si il marcam. Daca exista un varf w adiacent lui v (adica, daca exista muchia (vw) in graful orientat G, sau muchia in graful neorientat G) care nu a fost vizitat, alegem varful w ca noul punct de plecare si apelam recursiv procedura de parcurgere in adancime. La intoarcerea din apelul recursiv, daca exista un alt varf adiacent lui v care nu a fost vizitat, apelam din nou procedura etc. Cand toate varfurile adiacente lui v au fost marcate, se incheie consultarea inceputa in v. Daca au ramas varfuri in V care nu au fost vizitate, alegem unul din aceste varfuri si apelam procedura de parurgere. Continuam astfel, pana cand toate varfurile din V au fost marcate. Iata algoritmul:

procedure parcurge(G)
     for fiecare v 
I V do marca[v¬ nevizitat
     for fiecare v 
I V do
          if marca[v] = nevizitat then ad(v)

procedure ad(v)
    
     marca[v]
¬ vizitat
     for fiecare virf w adiacent lui v do
          if marca[w] = nevizitat then ad(w)

Acest mod de parcurgere se numeste “in adancime”, deoarece incearca sa initieze cat mai multe apeluri recursive inainte de a se intoarce dintr-un apel.

Parcurgerea in adancime a fost formulata cu mult timp in urma ca o tehnica de explorare a unui labirint. O persoana care cauta ceva intr-un labirint si aplica aceasta tehnica are avantajul ca “urmatorul loc in care cauta” este mereu foarte aproape.

Pentru graful din Figura 9.1a, presupunand ca pornim din varful 1 si ca vizitam vecinii unui varf in ordine numerica, parcurgerea varfurilor in adancime se face in ordinea: 1, 2, 3, 6, 5, 4, 7, 8.

http://www.cwu.edu/%7Eandonie/Cartea%20de%20algoritmi/images/cap9/image002.gif

Figura 9.1 Un graf neorientat si unul din arborii sai partiali.

Desigur, parcurgerea in adancime a unui graf nu este unica; ea depinde atat de alegerea varfului initial, cat si de ordinea de vizitare a varfurilor adiacente.

Cat timp este necesar pentru a parcurge un graf cu n varfuri si m muchii? Deoarece fiecare varf este vizitat exact o data, avem n apeluri ale procedurii ad. In procedura ad, cand vizitam un varf, testam marcajul fiecarui vecin al sau. Daca reprezentam graful prin liste de adiacenta, adica prin atasarea la fiecare varf a listei de varfuri adiacente lui, atunci numarul total al acestor testari este: m, daca graful este orientat, si 2m, daca graful este neorientat. Algoritmul necesita un timp in Q(n) pentru apelurile procedurii ad si un timp in Q(m) pentru inspectarea marcilor. Timpul de executie este deci in Q(max(mn)) = Q(m+n).

Daca reprezentam graful printr-o matrice de adiacenta, se obtine un timp de executie in Q(n2).

Parcurgerea in adancime a unui graf G, neorientat si conex, asociaza lui G un arbore partial. Muchiile arborelui corespund muchiilor parcurse in G, iar varful ales ca punct de plecare devine radacina arborelui. Pentru graful din Figura 9.1a, un astfel de arbore este reprezentat in Figura 9.1b prin muchiile “continue”; muchiile din G care nu corespund unor muchii ale arborelui sunt “punctate”. Daca graful G nu este conex, atunci parcurgerea in adancime asociaza lui G o padure de arbori, cate unul pentru fiecare componenta conexa a lui G.

Daca dorim sa si marcam numeric varfurile in ordinea parcurgerii lor, adaugam in procedura ad, la inceput:




num ¬ num 1
preord[v
¬ num

unde num este o variabila globala initializata cu zero, iar preord[1 .. n] este un tablou care va contine in final ordinea de parcurgere a varfurilor. Pentru parcurgerea din exemplul precedent, acest tablou devine:

1

2

3

6

5

4

7

8

Cu alte cuvinte, se parcurg in preordine varfurile arborelui partial din Figura 9.1b.

Se poate observa ca parcurgerea in adancime a unui arbore, pornind din radacina, are ca efect parcurgerea in preordine a arborelui.

Parcurgerea grafurilor in latime

Procedura de parcurgere in adancime, atunci cand se ajunge la un varf v oarecare, exploreaza prima data un varf w adiacent lui v, apoi un varf adiacent lui w etc. Pentru a efectua o parcurgere in latime a unui graf (orientat sau neorientat), aplicam urmatorul principiu: atunci cand ajungem intr-un varf oarecare v nevizitat, il marcam si vizitam apoi toate varfurile nevizitate adiacente lui v, apoi toate varfurile nevizitate adiacente varfurilor adiacente lui v etc. Spre deosebire de parcurgerea in adancime, parcurgerea in latime nu este in mod natural recursiva.

Pentru a putea compara aceste doua tehnici de parcurgere, vom da pentru inceput o versiune nerecursiva pentru procedura ad. Versiunea se bazeaza pe utilizarea unei stive. Presupunem ca avem functia ftop care returneaza ultimul varf inserat in stiva, fara sa il stearga. Folosim si functiile push si pop din Sectiunea 3.1.1.

procedure iterad(v)
     S ¬ stiva vida
     marca[v¬ vizitat
     push(vS)
     while S nu este vida do
          while exista un varf w adiacent lui ftop(S)
                   astfel incat marca[w] = nevizitat   do
              marca[w] ¬ vizitat
              push(wS)
          pop(S)

Pentru parcurgerea in latime, vom utiliza o coada si functiile insert-queue, delete-queue din Sectiunea 3.1.2 . Iata acum algoritmul de parcurgere in latime:

procedure lat(v)
     C ¬ coada vida
     marca[v¬ vizitat
     insert-queue(vC)
     while C nu este vida do
          ¬ delete-queue(C)
          for fiecare virf w adiacent lui u do
              if marca[w] = nevizitat  then  marca[w¬ vizitat
                                                              insert-queue(wC)

Procedurile iterad si lat trebuie apelate din procedura

procedure parcurge(G)
     for fiecare I V do marca[v¬ nevizitat
     for fiecare I V do
          if marca[v] = nevizitat then (v)

De exemplu, pentru graful din Figura 9.1, ordinea de parcurgere in latime a varfurilor este: 1, 2, 3, 4, 5, 6, 7, 8.

Ca si in cazul parcurgerii in adancime, parcurgerea in latime a unui graf G conex asociaza lui G un arbore partial. Daca G nu este conex, atunci obtinem o padure de arbori, cate unul pentru fiecare componenta conexa.

Analiza eficientei algoritmului de parcurgere in latime se face la fel ca pentru parcurgerea in adancime. Pentru a parcurge un graf cu n varfuri si m muchii timpul este in: i) Q(n+m), daca reprezentam graful prin liste de adiacenta; ii) Q(n2), daca reprezentam graful printr-o matrice de adiacenta.

Parcurgerea in latime este folosita de obicei atunci cand se exploreaza partial anumite grafuri infinite, sau cand se cauta cel mai scurt drum dintre doua varfuri.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1242
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site