Referat PARCURGEREA GRAFURILOR IN ADANCIME

Parcurgerea grafurilor n adncime Foarte muli algoritmi de prelucrare a grafurilor necesit examinarea tuturor nodurilor unui graf.Pentru aceasta este necesar definirea unei strategii de traversare a grafului.Se poate vorbi n principal de dou tehnici de traversare:-n adncime (Depth First)-n lime (Breadth First)n explicarea modului de funcionare a primei variante se folosete un ir de ntregi, VIZITAT, de lungime n cu ajutorul cruia se marcheaz nodurile deja vizitate pentru a evita trecerea de mai multe ori prin acelai nod.Cu alte cuvinte VIZITAT[j] = 1 dac nodul j a fost deja atins i VIZITAT[j] = 0 n caz contrar.Vom spune despre un nod i c a fost explorat dac are toate nodurile adiacente vizitate. Procedura recursiv care asigur parcurgerea unui graf n adncime ncepnd cu un anumit vrf i:Procedura Parcurgere_n_adncime(i) pentru toate vrfurile k adiacente cu vrful i executdaca vrful k este neparcurs atunci se parcurge vrful k apel parcurgere_n_adncime(k)Ieirea din recursivitate se produce n momentul n care nu se mai gsesc vrfuri neparcurse adiacente cu vrfurile parcurse deja. Este posibil ca dup un apel al procedurii incepnd cu un anumit vrf i s rmn n graf vrfuri neparcurse.n aceast situaie apelul procedurii se repet pentru un alt vrf iniial (dintre vrfurile neparcurse) pn la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie s asigure parcurgerea vrfului utilizat n apel.Condiiile interne care apar n problemele particulare de backtracking pot impune o parcurgere integral sau numai parial a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf n adncime:Procedura Backtracking(i) pentru toate vrfurile k adiacente cu vrful i executdaca vrful k este neparcurs i sunt ndeplinite condiiile de continuare atunci se parcurge vrful k se utilizeaza vrful k n soluie dac s-a ajuns la o soluie se afieaz apel Backtracking(k)Folosind aceast tehnic de traversare ne propunem s rspundem la ntrebarea:Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?Conform acestei metode explorarea unui nod este suspendat ori de cte ori un nou vrf este vizitat.Pentru graful G daca pornim din vrful 1, vizitarea nodurilor se va face n ordinea: 1,2,4,8,5,6,3,7.Urmtoarea funcie returneaz true dac graful este conex i false n caz contrar folosind tehnica parcurgerii n adncime:Function Conex: boolean;Procedura adncime(s) {parcurge graful in adancime}VIZITAT[s]:=1;pentru fiecare nod w adiacent cu s execut dac VIZITAT[w] = 0 atunci apel adncime(w) sfrit dac;sfrit pentru;sfrit procedura;pentru toate nodurile w execut VIZITAT[w]:=0;sfrit pentru; apel adncime(1); Conex:=true;pentru toate nodurile w executdac VIZITAT[w] = 0 atunci conex:=false; sfrit dac;sfrit pentru;Sfrit funcie;